Peichl, Timo and Vollmer, Heribert - Finite Automata with Generalized Acceptance Criteria

dmtcs:287 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, Vol. 4 no. 2
Finite Automata with Generalized Acceptance Criteria

Authors: Peichl, Timo and Vollmer, Heribert

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.


Source : oai:HAL:hal-00958956v1
Volume: Vol. 4 no. 2
Published on: January 1, 2001
Submitted 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]


Share

Browsing statistics

This page has been seen 65 times.
This article's PDF has been downloaded 44 times.