✦ LIBER ✦

Efficient implementation of regular languages using reversed alternating finite automata

✍ Scribed by K. Salomaa; X. Wu; S. Yu

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 93 KB
Volume: 231
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(99)00020-1

No coin nor oath required. For personal study only.

✦ Synopsis

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 have shown that this implementation is much more e cient than, for instance, the Grail DFA implementation in both space and time.