✦ LIBER ✦

Succinct representation of regular languages by boolean automata

✍ Scribed by Ernst Leiss

Publisher: Elsevier Science
Year: 1981
Tongue: English
Weight: 346 KB
Volume: 13
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(81)80005-9

No coin nor oath required. For personal study only.

✦ Synopsis

Boolean automata are a generalization of finite automata in the sense that the 'next state'i i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log2 m] states which accepts the reverse of the language accepted by A (m ~> 1). We also show that for every n ~> 1 there exists a boolean automaton with n states such that the smallest deterministic automaton accepting the same language has 2 (2") states; moreover this holds for an alphabet with only two letters.

📜 SIMILAR VOLUMES

On the Languages Representable by Finite

On the Languages Representable by Finite Probabilistic Automata

✍ Phan Dinh Diêu 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 837 KB

On Gödel speed-up and succinctness of la

On Gödel speed-up and succinctness of language representations

✍ J. Hartmanis 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 798 KB

Efficient implementation of regular lang

Efficient implementation of regular languages using reversed alternating finite automata

✍ K. Salomaa; X. Wu; S. Yu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 93 KB

Alternating ÿnite automata (AFA) provide a natural and succinct way to denote regular languages. We introduce a bit-wise representation of reversed AFA (r-AFA) transition functions and describe an e cient implementation method for r-AFA and their operations using this representation. Experiments hav

The single loop representations of regul

The single loop representations of regular languages

✍ H.J. Shyr; S.S. Yu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 782 KB

A regular language of the form UP' M' is called a single loop from the viewpoint of automata theory. It is known that every regular language can be expressed as (U,,,, U,L.;IV, )U F. where .4 is an index set, u,, ~1~ EX\*, c, EX~, i E A, and F is a finite set of words. This expression is called an s

Representations of (M, R)-systems by cat

Representations of (M, R)-systems by categories of automata

✍ M.W. Warner 📂 Article 📅 1982 🏛 Springer 🌐 English ⚖ 349 KB

Arbib in a paper entitled 'Categories of (M, R)-Systems' represents both simple (M, R)systems and those with varying genome as subcategories of the category of automata. An alternative characterisation of general (M, R)-systems as automata is proposed and two theorems on (M,R)-automata are proved. T

A kleene-like characterization of langua

A kleene-like characterization of languages accepted by systolic tree automata

✍ E. Fachini; A. Monti 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 686 KB

We present a Kleen-like characterization of the class of languages accepted by systolic binary tree automata, L(SBTA). This characterization uses union, intersection, restricted concatenation, restricted concatenation closure, and finite substitution closure. The restrictions we impose on the operat