Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334319 | Theoretical Computer Science | 2005 | 19 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Markus Holzer, Martin Kutrib,