zbMATH — the first resource for mathematics

Symbolic implementation of alternating automata. (English) Zbl 1160.68401
Ibarra, Oscar H. (ed.) et al., Implementation and application of automata. 11th international conference, CIAA 2006, Taipei, Taiwan, August 21–23, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-37213-4/pbk). Lecture Notes in Computer Science 4094, 208-218 (2006).
Summary: We show how to convert alternating Büechi automata to symbolic structures, using a variant of Miyano and Hayashi’s construction. We avoid building the nondeterministic equivalent of the alternating automaton, thus save an exponential factor in space.
For one-weak automata, Miyano and Hayashi’s approach produces automata that are larger than needed. We show a hybrid approach that produces a smaller nondeterministic automaton if part of the alternating automaton is one weak.
We perform a thorough experimental analysis and conclude that the symbolic approach outperforms the explicit one.
For the entire collection see [Zbl 1113.68007].

68Q45 Formal languages and automata
Full Text: DOI