Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
From MaRDI portal
Publication:3149086
DOI10.1051/ita:2001106zbMath1010.68068WikidataQ61677534 ScholiaQ61677534MaRDI QIDQ3149086
Carlo Mereghetti, Giovanni Pighizzini, Beatrice Palano
Publication date: 14 May 2003
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_5_477_0
68Q45: Formal languages and automata
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q19: Descriptive complexity and finite models
Related Items
On the Size of One-way Quantum Finite Automata with Periodic Behaviors, Quantum State Complexity of Formal Languages, GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA, Descriptional complexity of iterated uniform finite-state transducers, Unnamed Item, Iterated uniform finite-state transducers on unary languages, Quantum finite automata: advances on Bertoni's ideas, Iterated uniform finite-state transducers on unary languages, Unary probabilistic and quantum automata on promise problems, Removing nondeterminism in constant height pushdown automata, Quantum automata for some multiperiodic languages, Small size quantum automata recognizing some regular languages, Complexity of Promise Problems on Classical and Quantum Automata, From Quantum Query Complexity to State Complexity, One-Way Finite Automata with Quantum and Classical States, Quantum finite automata with control language
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite automata and unary languages
- Quantum automata and quantum grammars
- Optimal Simulations between Unary Automata
- Characterizations of 1-Way Quantum Finite Automata
- Alternating Pushdown and Stack Automata
- On the maximal order in $S_n$ and $S*_n$
- Alternation
- Probabilistic automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
