Various Aspects of Finite Quantum Automata

1. Ablayev, F., Gainutdinova, A.: On the Lower Bounds for One-Way Quantum Automata. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 132–140. Springer, Heidelberg (2000)

   Chapter  Google Scholar 

2. Ambainis, A., Beaudry, M., Golovkins, M., Ķikusts, A., Mercer, M., Thérien, D.: Algebraic Results on Quantum Automata. Theory of Computing Systems 39, 165–188 (2006)

   Google Scholar 

3. Ambainis, A., Bonner Rūsiņš, R.F., Ķikusts, A.: Probabilities to Accept Languages by Quantum Finite Automata. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 174–185. Springer, Heidelberg (1999)

   Google Scholar 

4. Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th FOCS, pp. 376–383 (1998)

   Google Scholar 

5. Ambainis, A., Ķikusts, A., Valdats, M.: On the class of languages recognizable by 1-way quantum finite automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 75–86. Springer, Heidelberg (2001)

   Google Scholar 

6. Ambainis, A., Ķikusts, A.: Exact results for accepting probabilities of quantum automata. Theoretical Computer Science 295(1), 3–25 (2003)

   Google Scholar 

7. Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM Journal on Computing 26(5), 1411–1473 (1997)

   Article  MATH  MathSciNet  Google Scholar 

8. Blondel, V.D., Canterini, V.: Undecidable problems for probabilistic automata of fixed dimension. Theory of Computing systems 36, 231–245 (2003)

   Article  MATH  MathSciNet  Google Scholar 

9. Blondel, V.D., Jeandel, E., Koiran, P., Portier, N.: Decidable and undecidable problems about quantum automata. SIAM Journal on Computing 34(6), 1464–1473 (2005)

   Article  MATH  MathSciNet  Google Scholar 

10. Brodsky, A., Pippenger, N.: Characterizations of 1-Way Quantum Finite Automata. SIAM Journal on Computing 31(5), 1456–1478 (2002)

    Article  MATH  MathSciNet  Google Scholar 

11. Church, A.: An unsolvable problem in elementary number theory. American Journal of Mathematics 58, 345–363 (1936)

    Article  MathSciNet  Google Scholar 

12. Clay Mathematics Institute, http://www.claymath.org/

13. Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the Third Annual ACM Symposium on the Theory of Computing, pp. 151–158. ACM, New York (1971)

    Chapter  Google Scholar 

14. Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A 400, 97–117 (1985)

    Article  MATH  MathSciNet  Google Scholar 

15. Eilenberg, S.: Automata, languages, and machines, vol. A. Academic Press, London (1974)

    MATH  Google Scholar 

16. Feynman, R.P.: Simulating physics with computers. International Journal of Theoretical Physics 21(6/7), 467–488 (1982)

    Article  MathSciNet  Google Scholar 

17. Freivalds, R.: Non-constructive Methods for Finite Probabilistic Automata. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 169–180. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

18. Gödel, K.: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38, 173–198 (1931)

    Article  Google Scholar 

19. Hirvensalo, M.: Quantum Computing, 2nd edn. Springer, Heidelberg (2004)

    MATH  Google Scholar 

20. Hirvensalo, M.: Some Open Problems Related to Quantum Computing. In: Paun, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science – The Challenge of the New Century, vol. 1. World Scientific, Singapore (2004)

    Google Scholar 

21. Hirvensalo, M.: Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 309–319. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

22. Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, pp. 66–75 (1997)

    Google Scholar 

23. Matiyasevich, Y., Sénizergues, G.: Decision problems for semi-Thue systems with a few rules. Theoretical Computer Science 330(1), 145–169 (2005)

    Article  MATH  MathSciNet  Google Scholar 

24. Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoretical Computer Science 237(1-2), 275–306 (2000)

    Article  MATH  MathSciNet  Google Scholar 

25. Paterson, M.S.: Unsolvability in 3 X 3 matrices. Studies in Applied Mathematics 49, 105–107 (1970)

    MATH  MathSciNet  Google Scholar 

26. Paz, A.: Introduction to Probabilistic Automata. Academic Press, London (1971)

    MATH  Google Scholar 

27. Post, E.L.: A variant of a recursively unsolvable problem. Bulletin of American Mathematical Society 52, 264–268 (1946)

    Article  MATH  MathSciNet  Google Scholar 

28. Razborov, A.A., Rudich, S.: Natural Proofs. Journal of Computer and System Sciences 55, 24–25 (1997)

    Article  MATH  MathSciNet  Google Scholar 

29. Tarski, A.: A decision method for elementary algebra and geometry. University of California Press (1951)

    Google Scholar 

30. Turakainen, P.: Generalized automata and stochastic languages. Proceedings of American Mathematical Society 21, 303–309 (1969)

    Article  MATH  MathSciNet  Google Scholar 

31. Turing, A.M.: On Computable Numbers, With an Application to the Entscheidungsproblem. Proc. London Math. Soc. 2(42), 230–265 (1936)

    Google Scholar 

32. Rozenberg, G., Salomaa, A.: Regular Languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Word, Language, Grammar, vol. 1, Springer, Heidelberg (1997)

    Google Scholar 

Download references