Finite Automata with Generalized Acceptance Criteria

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.179-192
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958956
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:53:03
Dernière modification le : mercredi 10 octobre 2018 - 20:44:13
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:04:34

Fichier

dm040210.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958956, version 1

Collections

Citation

Timo Peichl, Heribert Vollmer. Finite Automata with Generalized Acceptance Criteria. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.179-192. 〈hal-00958956〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

619