Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Descriptional Complexity of Operations on Alternating and Boolean Automata
verfasst von : Galina Jirásková
Erschienen in: Computer Science – Theory and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The paper shows that the tight bound for the conversion of alternating finite automata into nondeterministic finite automata with a single initial state is 2
n
+ 1. This solves an open problem stated by Fellah
et al.
(Intern. J. Computer Math. 35, 1990, 117–132). Then we examine the complexity of basic operations on languages represented by boolean and alternating finite automata. We get tight bounds for intersection and union, and for concatenation and reversal of languages represented by boolean automata. In the case of star, and of concatenation and reversal of AFA languages, our upper and lower bounds differ by one.