Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958956
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:53:03 PM
Last modification on : Wednesday, October 10, 2018 - 8:44:13 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:04:34 PM

File

dm040210.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

229

Files downloads

1522