Undecidability on quantum finite automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Undecidability on quantum finite automata

Full text

Pdf (568 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 368 - 375

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Masami Amano	School of Informatics, Kyoto University, Kyata 606-8501, Japan
Kazuo Iwama	School of Informatics, Kyoto University, Kyata 606-8501, Japan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 29, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301344 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AF98	Andris Ambainis , Rusins Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalizations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.332, November 08-11, 1998
	DS89	C. Dwork and L. Stockmeyer, "On the power of 2- way probabilistic finite automata," Proceedings of the 30th IEEE Conference on Foundations of Computer Science, 480-485, 1989.
	Fre81	Rusins Freivalds, Probabilistic Two-Way Machines, Proceedings on Mathematical Foundations of Computer Science, p.33-45, August 31-September 04, 1981
	Gro96	Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
	HU79	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	HU68	J. Hopcroft and J. Ullman, "Deterministic stack automata and the quotient operator," JCSS, 2:1, 1-12, t 968.
	KW97	A. Kondacs , J. Watrous, On the power of quantum finite state automata, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.66, October 19-22, 1997
	Min66	Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
	Sho94	P. Shot, "Algorithms for quantum computation: discrete logarithms and factoring," Proceedings o} the 35th IEEE Symposium on Foundations of Computer Science, 124-134, 1994.

CITED BY 6

	Tomohiro Yamasaki , Hirotada Kobayashi , Hiroshi Imai, Quantum versus deterministic counter automata, Theoretical Computer Science, v.334 n.1-3, p.275-297, 11 April 2005
	Zhengjun Xi , Xin Wang , Yongming Li, Some algebraic properties of measure-once two-way quantum finite automata, Quantum Information Processing, v.7 n.5, p.211-225, October 2008
	Lvzhou Li , Daowen Qiu, Determining the equivalence for one-way quantum finite automata, Theoretical Computer Science, v.403 n.1, p.42-51, August, 2008
	Harumichi Nishimura , Tomoyuki Yamakami, An application of quantum finite automata to interactive proof systems, Journal of Computer and System Sciences, v.75 n.4, p.255-269, June, 2009
	Lvzhou Li , Daowen Qiu, Note: A note on quantum sequential machines, Theoretical Computer Science, v.410 n.26, p.2529-2535, June, 2009
	Daowen Qiu , Sheng Yu, Hierarchy and equivalence of multi-letter quantum finite automata, Theoretical Computer Science, v.410 n.30-32, p.3006-3017, August, 2009