On a Conjecture by Christian Choffrut
From MaRDI portal
Publication:4605510
DOI10.1142/S0129054117400032zbMath1380.68245OpenAlexW2775545689WikidataQ122876952 ScholiaQ122876952MaRDI QIDQ4605510
Aleksandrs Belovs, Abuzer Yakaryılmaz, Juan Andrés Montoya
Publication date: 22 February 2018
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054117400032
nondeterminismcounting problemstate complexitypromise problemsaffine automatonzero-errorquantum automatonalternating automatonultrametric automaton
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Related Items
Computational limitations of affine automata and generalized affine automata, Error-Free Affine, Unitary, and Probabilistic OBDDs, New Results on Vector and Homing Vector Automata, Improved constructions for succinct affine automata
Cites Work
- Unnamed Item
- Unnamed Item
- Superiority of exact quantum automata for promise problems
- Unbounded-error quantum computation with small space bounds
- On free subgroups of semi-simple groups
- Separating strings with small automata
- Intersection and union of regular languages and state complexity
- Quantum automata and quantum grammars
- Two-way finite automata with quantum and classical states.
- Looking for Pairs that Hard to Separate: A Quantum Approach
- About Goto's method showing surjectivity of word maps
- Counting with Probabilistic and Ultrametric Finite Automata
- Quantum Finite Automata: A Modern Introduction
- Notes on counting with finite machines
- Quantum Computation and Quantum Information
- Communication Complexity
- Convergent Sequences in Discrete Groups
- Remarks on Separating Words
- Ultrametric Finite Automata and Turing Machines
- Probabilistic automata
- Affine Computation and Affine Automaton
