Finite Automata with Generalized Acceptance CriteriaReportar como inadecuado

Finite Automata with Generalized Acceptance Criteria - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Theoretische Informatik Würzburg

Abstract : 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.

Keywords : finite automata generalized acceptance criteria leaf language formal languages complexity classes

Autor: Timo Peichl - Heribert Vollmer -



Documentos relacionados