Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

DOI10.1051/ita:2001106zbMath1010.68068OpenAlexW2004312423WikidataQ61677534 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

zbMATH Keywords

unary automatacyclic languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Descriptive complexity and finite models (68Q19)

Related Items (16)

Unary probabilistic and quantum automata on promise problems ⋮ Iterated uniform finite-state transducers on unary languages ⋮ One-Way Finite Automata with Quantum and Classical States ⋮ On the Size of One-way Quantum Finite Automata with Periodic Behaviors ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ From Quantum Query Complexity to State Complexity ⋮ Unnamed Item ⋮ GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Quantum automata for some multiperiodic languages ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Small size quantum automata recognizing some regular languages ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Quantum State Complexity of Formal Languages ⋮ Quantum finite automata with control language

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata