𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Alternating finite automata and star-free languages

✍ Scribed by Kai Salomaa; Sheng Yu

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
96 KB
Volume
234
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

For a given extended regular expression e we construct an equational representation of an alternating ΓΏnite automaton accepting the language denoted by e. For star-free extended regular expressions the construction yields a loop-free alternating ΓΏnite automaton. Also the inclusion in the opposite direction holds and, thus, we obtain a new characterization for the class of star-free languages.

πŸ“œ SIMILAR VOLUMES

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