Quantum versus deterministic counter automata

DOI10.1016/j.tcs.2004.07.034zbMath1080.68060OpenAlexW1968294243MaRDI QIDQ1779306

Hirotada Kobayashi, Tomohiro Yamasaki, Hiroshi Imai

Publication date: 1 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.07.034

zbMATH Keywords

Quantum computingAutomata theoryCounter automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items

Classical and Quantum Counter Automata on Promise Problems ⋮ Quantum Pushdown Automata with Garbage Tape ⋮ QUANTUM COUNTER AUTOMATA ⋮ Quantum computation with write-only memory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Universality of a reversible two-counter machine
• Exact results for accepting probabilities of quantum automata.
• Quantum automata and quantum grammars
• Reversible space equals deterministic space
• SOFSEM 2000: Theory and practice of informatics. 27th conference on current trends in theory and practice of informatics, Milovy, Czech Republic, November 25--December 2, 2000. Proceedings
• Two-way finite automata with quantum and classical states.
• One-way probabilistic reversible and quantum one-counter automata.
• Undecidability on quantum finite automata
• Characterizations of 1-Way Quantum Finite Automata
• Dense quantum coding and quantum finite automata
• Two-Way Counter Machines and Diophantine Equations
• Counter machines and counter languages