Timo Peichl ; Heribert Vollmer - Finite Automata with Generalized Acceptance Criteria

dmtcs:287 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, Vol. 4 no. 2 - https://doi.org/10.46298/dmtcs.287
Finite Automata with Generalized Acceptance CriteriaArticle

Authors: Timo Peichl 1; Heribert Vollmer ORCID1

  • 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.

Volume: Vol. 4 no. 2
Published on: January 1, 2001
Imported on: March 26, 2015
Keywords: finite automata,generalized acceptance criteria,leaf language,formal languages,complexity classes,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 335 times.
This article's PDF has been downloaded 445 times.