Paper Info
Title
On the descriptional complexity of finite automata with modified acceptance conditions
Abstract
We consider deterministic and nondeterministic finite automata with acceptance conditions that rely on the whole history of a computation on a given word and not only on the last state of the computation under consideration. Formally, these conditions can be seen as the natural analogies of the Büchi and Muller acceptance for finite automata on infinite words. We study the computational power of these new acceptance mechanisms and prove some results on the descriptional complexity of conversions between automata with these new acceptance criteria and finite automata with ordinary acceptance.
Year
DOI
Venue
2003
10.1016/j.tcs.2004.06.030
Theoretical Computer Science - Descriptional complexity of formal systems
Keywords
DocType
Volume
Computational power,finite automaton,infinite word,descriptional complexity,Muller acceptance,computational power,new acceptance mechanism,Finite automata,new acceptance criterion,acceptance condition,modified acceptance condition,Acceptance conditions,ordinary acceptance,nondeterministic finite automaton,Descriptional complexity
Conference
330
Issue
ISSN
Citations 
2
0304-3975
0
PageRank 
References 
Authors
0.34
19
2
Name
Order
Citations
PageRank
Markus Holzer113812.30
Martin Kutrib277889.77