Unary Probabilistic and Quantum Automata on Promise Problems

1. Ablayev, F., Gainutdinova, A., Khadiev, K., Yakaryılmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 53–64. Springer, Heidelberg (2014)

   Google Scholar 

2. 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 

3. Ablayev, F., Gainutdinova, A.: Complexity of quantum uniform and nonuniform automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 78–87. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

4. Ablayev, F.M., Gainutdinova, A., Karpinski, M., Moore, C., Pollett, C.: On the computational power of probabilistic and quantum branching program. Information Computation 203(2), 145–162 (2005)

   Article  MathSciNet  Google Scholar 

5. Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: FOCS 1998, pp. 332–341 (1998)

   Google Scholar 

6. Ambainis, A., Yakaryılmaz, A.: Superiority of exact quantum automata for promise problems. Information Processing Letters 112(7), 289–291 (2012)

   Article  MathSciNet  Google Scholar 

7. Apostol, T.M.: Introduction to Analytic Number Theory. Springer (1976)

   Google Scholar 

8. Bianchi, M.P., Mereghetti, C., Palano, B.: Complexity of promise problems on classical and quantum automata. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Gruska Festschrift. LNCS, vol. 8808, pp. 161–175. Springer, Heidelberg (2014)

   Google Scholar 

9. Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs (extended abstract). In: FOCS 1989, pp. 462–467 (1989)

   Google Scholar 

10. Gainutdinova, A., Yakaryilmaz, A.: Unary probabilistic and quantum automata on promise problems. Technical Report arxiv.org/abs/1502.01462, arXiv (2015)

    Google Scholar 

11. Geffert, V., Yakaryılmaz, A.: Classical automata on promise problems. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 126–137. Springer, Heidelberg (2014)

    Google Scholar 

12. Goldreich, O.: On promise problems: a survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254–290. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

13. Gruska, J., Qiu, D., Zheng, S.: Generalizations of the distributed Deutsch-Jozsa promise problem. Technical report, arXiv (2014). arXiv:1402.7254

14. Gruska, J., Qiu, D., Zheng, S.: Potential of quantum finite automata with exact acceptance. Technical Report arXiv:1404.1689 (2014)

15. Hirvensalo, M.: Quantum automata with open time evolution. International Journal of Natural Computing 1(1), 70–85 (2010)

    Article  Google Scholar 

16. Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Van Nostrand, Princeton (1960)

    Google Scholar 

17. Klauck, H.: On quantum and probabilistic communication: las vegas and one-way protocols. In: STOC 2000, pp. 644–651 (2000)

    Google Scholar 

18. Mereghetti, C., Palano, B., Pighizzini, G.: Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata. Theoretical Informatics and Applications 35(5), 477–490 (2001)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

20. Murakami, Y., Nakanishi, M., Yamashita, S., Watanabe, K.: Quantum versus classical pushdown automata in exact computation. IPSJ Digital Courier 1, 426–435 (2005)

    Article  Google Scholar 

21. Nakanishi, M.: Quantum pushdown automata with a garbage tape. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015-Testing. LNCS, vol. 8939, pp. 352–363. Springer, Heidelberg (2015)

    Google Scholar 

22. Nakanishi, M., Yakaryılmaz, A.: Classical and quantum counter automata on promise problems (2014). (arXiv:1412.6761) (Accepted to CIAA2015)

    Google Scholar 

23. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000)

    Google Scholar 

24. Rashid, J., Yakaryılmaz, A.: Implications of quantum automata for contextuality. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 318–331. Springer, Heidelberg (2014)

    Google Scholar 

25. Salomaaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and monographs in computer science. Springer-Verlag (1978)

    Google Scholar 

26. Cem Say, A.C., Yakaryılmaz, A.: Quantum finite automata: a modern introduction. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Gruska Festschrift. LNCS, vol. 8808, pp. 208–222. Springer, Heidelberg (2014)

    Google Scholar 

27. Watrous, J.: Encyclopedia of Complexity and System Science. In: Quantum computational complexity (chapter). Springer (2009). arXiv:0804.3401

28. Yakaryılmaz, A., Cem Say, A.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Information and Computation 10(9&10), 747–770 (2010)

    MathSciNet  Google Scholar 

29. Yakaryılmaz, A., Cem Say, A.C.: Unbounded-error quantum computation with small space bounds. Information and Computation 279(6), 873–892 (2011)

    Article  Google Scholar 

30. Zheng, S., Gruska, J., Qiu, D.: On the state complexity of semi-quantum finite automata. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 601–612. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

31. Zheng, S., Qiu, D., Gruska, J., Li, L., Mateus, P.: State succinctness of two-way finite automata with quantum and classical states. Theoretical Computer Science 499, 98–112 (2013)

    Article  MathSciNet  Google Scholar 

Download references