Quantum versus deterministic counter automata

DOI10.1016/J.TCS.2004.07.034MaRDI QIDQ1779306zbMATH OpenOpenAlexFDO

Authors Tomohiro Yamasaki, Hirotada Kobayashi, Hideki 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)

Recommendations

• scientific article; zbMATH DE number 2090014
• scientific article; zbMATH DE number 2080917
• Quantum counter automata

Cites work

• scientific article; zbMATH DE number 1688355 (Why is no real title available?)
• scientific article; zbMATH DE number 2080917 (Why is no real title available?)
• scientific article; zbMATH DE number 2080922 (Why is no real title available?)
• scientific article; zbMATH DE number 1490003 (Why is no real title available?)
• scientific article; zbMATH DE number 1490010 (Why is no real title available?)
• scientific article; zbMATH DE number 1759400 (Why is no real title available?)
• scientific article; zbMATH DE number 1405684 (Why is no real title available?)
• Characterizations of 1-Way Quantum Finite Automata
• Counter machines and counter languages
• Dense quantum coding and quantum finite automata
• Exact results for accepting probabilities of quantum automata.
• One-way probabilistic reversible and quantum one-counter automata.
• Quantum automata and quantum grammars
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• 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 Counter Machines and Diophantine Equations
• Two-way finite automata with quantum and classical states.
• Undecidability on quantum finite automata
• Universality of a reversible two-counter machine

Cited in

(9)

• scientific article; zbMATH DE number 2090014 (Why is no real title available?)
• Exact Affine Counter Automata
• Quantum pushdown automata with garbage tape
• Superiority of one-way and realtime quantum machines
• Quantum counter automata
• One-counter verifiers for decidable languages
• scientific article; zbMATH DE number 1696659 (Why is no real title available?)
• scientific article; zbMATH DE number 2080917 (Why is no real title available?)
• scientific article; zbMATH DE number 1490010 (Why is no real title available?)

This page was built for publication: Quantum versus deterministic counter automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1779306)