Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
DOI10.1051/ITA:2001106zbMATH Open1010.68068DBLPjournals/ita/MereghettiPP01OpenAlexW2004312423WikidataQ61677534 ScholiaQ61677534MaRDI QIDQ3149086FDOQ3149086
Authors: Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini 
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
Recommendations
- Succinctness of two-way probabilistic and quantum finite automata
- The complexity of probabilistic versus quantum finite automata
- On the complexity of minimizing probabilistic and quantum automata
- Various Aspects of Finite Quantum Automata
- scientific article; zbMATH DE number 6440119
- State succinctness of two-way finite automata with quantum and classical states
- Approximate determinization of quantitative automata
- Quantum finite automata and linear context-free languages: a decidable problem
- scientific article; zbMATH DE number 1405684
- Nondeterministic finite automata based on quantum logic: language equivalence relation and robustness
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Descriptive complexity and finite models (68Q19)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Probabilistic automata
- Title not available (Why is that?)
- Alternation
- Finite automata and unary languages
- Title not available (Why is that?)
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Quantum automata and quantum grammars
- Characterizations of 1-Way Quantum Finite Automata
- Title not available (Why is that?)
- Optimal simulations between unary automata
- On the maximal order in $S_n$ and $S*_n$
- Title not available (Why is that?)
- Alternating Pushdown and Stack Automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (21)
- Iterated uniform finite-state transducers on unary languages
- Counting with probabilistic and ultrametric finite automata
- From quantum query complexity to state complexity
- Descriptional complexity of iterated uniform finite-state transducers
- The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
- Mathematical Foundations of Computer Science 2003
- Quantum state complexity of formal languages
- More on quantum, stochastic, and pseudo stochastic languages with few states
- Behaviours of unary quantum automata
- Title not available (Why is that?)
- 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
- Iterated uniform finite-state transducers on unary languages
- Quantum automata for some multiperiodic languages
- Small size quantum automata recognizing some regular languages
- Removing nondeterminism in constant height pushdown automata
- On the size of unary probabilistic and nondeterministic automata
- Quantum finite automata with control language
- GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
- Quantum finite automata: advances on Bertoni's ideas
This page was built for publication: Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149086)
