Finite Automata with Generalized Acceptance CriteriaArticle
Authors: Timo Peichl 1; Heribert Vollmer 1
NULL##0000-0002-9292-1960
Timo Peichl;Heribert Vollmer
1 Theoretische Informatik [Würzburg]
We examine the power of nondeterministic finite automata with acceptance of an input word defined by a leaf language, i.e., a condition on the sequence of leaves in the automaton's computation tree. We study leaf languages either taken from one of the classes of the Chomsky hierarchy, or taken from a time- or space-bounded complexity class. We contrast the obtained results with those known for leaf languages for Turing machines and Boolean circuits.