FANDOM


This is a list of published papers on quantum automata. The papers are classified by the years of publication.

1997: Edit

[KW97] Attila Kondacs and John Watrous. “On the power of quantum finite state automata”. In: FOCS. IEEE, 1997, pp. 66–75.

[Wat97] John Watrous. On the Power of 2-Way Quantum Finite State Automata. Tech. rep. CS-TR-1997-1350. Permanent link: http://digital.library.wisc.edu/1793/60124. University of Wisconsin, 1997.

1998: Edit

[AF98] Andris Ambainis and Rūsiņš Freivalds. “1-way quantum finite automata: strengths, weaknesses and generalizations”. In: FOCS. (arXiv:quant-ph/9802062). IEEE, 1998, pp. 332–341.

[ANV98] Andris Ambainis, Ashwin Nayak, and Umesh Vazirani. On the space-efficiency of 1-way quantum finite automata. Tech. rep. arXiv:quant-ph/9804043v1. 1998.

[Bro98] Alex Brodsky. “Models and characterizations of 1-way quantum finite automata”. MA thesis. The University of British Columbia, 1998.

[Kik98] Arnolds Ķikusts. A small 1-way quantum finite automaton. Tech. rep. arXiv:quant-ph/-9810065v1. 1998.

[WC08] Karoline Wiesner and James P. Crutchfield. “Computation in finitary stochastic and quantum processes”. In: Physica D: Nonlinear Phenomena 237.9 (2008), pp. 1173–1195.

1999: Edit

[ABFGK99] Andris Ambainis et al. “Quantum Finite Multitape Automata”. In: SOFSEM. Vol. 1725. LNCS. (arXiv:quant-ph/9905026). 1999, pp. 340–348.

[ABFK99] Andris Ambainis et al. “Probabilities to Accept Languages by Quantum Finite Automata”. In: COCOON. Vol. 1627. LNCS. (arXiv:quant-ph/9904066). 1999, pp. 174–183.

[AI99] Masami Amano and Kazuo Iwama. “Undecidability on quantum finite automata”. In: STOC. ACM, 1999, pp. 368–375.

[ANTV99] Andris Ambainis et al. “Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata”. In: STOC. ACM, 1999, pp. 376–383.

[Gud99] Stanley Gudder. “Quantum Automata: An Overview”. In: International Journal of Theoretical Physics 38.9 (1999), pp. 2261–2282.

[Kr99] Maksim Kravtsev. “Quantum Finite One-Counter Automata”. In: SOFSEM. Vol. 1725. LNCS. 1999, pp. 431–441.

[Nay99] Ashwin Nayak. “Optimal Lower Bounds for Quantum Automata and Random Access Codes”. In: FOCS. IEEE, 1999, pp. 369–376.

2000: Edit

[AG00] Farid M. Ablayev and Aida Gainutdinova. “On the Lower Bounds for One-Way Quantum Automata”. In: MFCS. Vol. 1893. LNCS. 2000, pp. 132–140.

[Gol00] Marats Golovkins. “Quantum Pushdown Automata”. In: SOFSEM. Vol. 1963. LNCS. (arXiv:-quant-ph/0102054). 2000, pp. 336–346.

[Gru00] Jozef Gruska. “Descriptional Complexity Issues in Quantum Computing”. In: Journal of Automata, Languages and Combinatorics 5.3 (2000), pp. 191–218.

[GV00A] Jozef Gruska and Roland Vollmar. “QUANTUM MODELS AND MODES OF COMPUTATION AND COMMUNICATION”. In: Algebraic Systems, Formal Languages and Computations. Vol. 1166. (http://hdl.handle.net/2433/64353). 2010, pp. 76–85.

[GV00B] Jozef Gruska and Roland Vollmar. “Quantum Finite Automata”. In: Words, Languages & Combinatorics. World Scientific, 2000, pp. 192–211.

[Gud00A] Stanley Gudder. “Quantum computers”. In: International Journal of Theoretical Physics 39.9 (2002), pp. 2151–2177.

[Gud00B] Stanley Gudder. “Basic Properties of Quantum Automata”. In: Foundations of Physics 30.2 (2000), pp. 301–319.

[Kla00] Hartmut Klauck. “On quantum and probabilistic communication: Las Vegas and one-way protocols”. In: STOC. (See also http://www.thi.informatik.uni-frankfurt.de/ klauck/stoc00.ps). ACM, 2000, pp. 644–651.

[MC00] Cristopher Moore and James P. Crutchfield. “Quantum automata and quantum grammars”. In: Theoretical Computer Science 237.1-2 (2000), pp. 275–306.

[Pa00] Kathrin Paschen. Quantum finite automata using ancilla qubits. Tech. rep. (http://digbib.-ubka.uni-karlsruhe.de/volltexte/documents/756861). University of Karlsruhe, 2000.

[YKTI00] Tomohiro Yamasaki et al. “One-Way Probabilistic Reversible and Quantum One-Counter Automata”. In: COCOON. Vol. 1858. LNCS. 2000, pp. 436–446.

2001: Edit

[AK01] Andris Ambainis and Arnolds Ķikusts. “Exact Results for Accepting Probabilities of Quantum Automata”. In: MFCS. Vol. 2136. LNCS. 2001, pp. 135–147.

[AKV01] Andris Ambainis, Arnolds Ķikusts, and Māris Valdats. “On the Class of Languages Recognizable by 1-Way Quantum Finite Automata”. In: STACS. Vol. 2010. LNCS. 2001, pp. 75–86.

[BB01] Aija Berzina and Richard F. Bonner. “Ambainis-Freivalds’ Algorithm for Measure-Once Automata”. In: FCT. Vol. 2138. LNCS. 2001, pp. 83–93.

[BC01A] Alberto Bertoni and Marco Carpentieri. “Regular languages accepted by quantum automata”. In: Information and Computation 165.2 (2001), pp. 174–182.

[BC01B] Alberto Bertoni and Marco Carpentieri. “Analogies and differences between quantum and stochastic automata”. In: Theoretical Computer Science 262.1-2 (2001), pp. 69–81.

[BFK01] Richard F. Bonner, Rūsiņš Freivalds, and Maksim Kravtsev. “Quantum versus Probabilistic One-Way Finite Automata with Counter”. In: SOFSEM. Vol. 2234. LNCS. 2001, pp. 181– 190.

[Cia01] Massimo Pica Ciamarra. “Quantum Reversibility and a New Model of Quantum Automaton”. In: FCT. Vol. 2138. LNCS. 2001, pp. 376–379.

[Dub01] Andrej Dubrovsky. “Space-Efficient 1.5-Way Quantum Turing Machine”. In: FCT. Vol. 2138. LNCS. 2001, pp. 380–383.

[FW01] Rūsiņš Freivalds and Andreas Winter. “Quantum Finite State Transducers”. In: SOFSEM. Vol. 2234. LNCS. (arXiv:quant-ph/0011052). 2001, pp. 233–242.

[Gru01] Jozef Gruska. “Quantum implementations of quantum automata”. In: Decoherence and its implications in quantum computation and information transfer. Ed. by Tony Gonis and Patrice E. A. Truchi. IOS Press, 2001, pp. 329–346.

[Kos01] Takeshi Koshiba. “Polynomial-Time Algorithms for the Equivalence for One-Way Quantum Finite Automata”. In: ISAAC’01. Vol. 2223. LNCS. 2001, pp. 268–278.

[MP01] Carlo Mereghetti and Beatrice Palano. “Upper Bounds on the Size of One-Way Quantum Finite Automata”. In: ICTCS. Vol. 2202. LNCS. 2001, pp. 123–135.

[MPP01A] Carlo Mereghetti, Beatrice Palano, and Giovanni Pighizzini. “On the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata”. In: Proceedings of 3rd International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS’01). 2001, pp. 141–148.

[MPP01B] Carlo Mereghetti, Beatrice Palano, and Giovanni Pighizzini. “Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata”. In: Theoretical Informatics and Applications 35.5 (2001), pp. 477–490.

[NIH01] Masaki Nakanishi, Takao Indoh, and Kiyoharu Hamaguchi. On the Power of Quantum Pushdown Automata with a Classical Stack and 1.5-way Quantum Finite Automata. Tech. rep. NAIST-IS-TR2001005. Nara Institute of Science and Technology, 2001.

2002: Edit

[AIP02] Masami Amano, Kazuo Iwama, and Raymond H. Putra. “Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations”. In: UMC. Vol. 2509. LNCS. 2002, pp. 100–114.

[ANTV02] Andris Ambainis et al. “Dense quantum coding and quantum finite automata”. In: Journal of the ACM 49.4 (2002), pp. 496–511. issn: 0004-5411.

[AW02] Andris Ambainis and John Watrous. “Two–way finite automata with quantum and classical states”. In: Theoretical Computer Science 287.1 (2002), pp. 299–311.

[BF02] Richard Bonner and Rūsiņš Freivalds. “Quantum Learning by Finite Automata”. In: Proceedings of International Workshop on Quantum Computation and Learning. 2002, pp. 85–96.

[BFR02] Richard Bonner, Rūsiņš Freivalds, and Zigmārs Rasščevskis. “On the size of finite probabilistic and quantum automata”. In: Proceedings of International Workshop on Quantum Computation and Learning. 2002, pp. 19–25.

[BP02] Alex Brodsky and Nicholas Pippenger. “Characterizations of 1-Way Quantum Finite Automata”. In: SIAM Journal on Computing 31.5 (2002), pp. 1456–1478.

[DS02] Andrej Dubrovsky and Oksana Scegulnaja. “Quantum Automata with Mixed States: Function Computation and Language Recognition”. In: Proceedings of International Workshop on Quantum Computation and Learning. 2002, pp. 62–66.

[GK02] Marats Golovkins and Maksim Kravtsev. “Probabilistic Reversible Automata and Quantum Automata”. In: COCOON. Vol. 2387. LNCS. 2002, pp. 574–583.

[GB02] S. Gudder and R. Ball. “Properties of Quantum Languages”. In: International Journal of Theoretical Physics 41.4 (2002), pp. 569–591.

[Jea02] Emmanuel Jeandel. “Indécidabilité sur les automates quantiques”. Available at ftp://ftp.enslyon.fr/pub/LIP/Rapports/DEA/DEA2002/DEA2002-02.ps.gz. MA thesis. ENS Lyon, 2002.

[Luc02] Alexey Luchko. “Generation of Quantum Finite Automata by Genetic Programming”. In: Proceedings of International Workshop on Quantum Computation and Learning. 2002, pp. 71– 73.

[Mi02] Gatis Midrijānis. “The Complexity of Probabilistic versus Quantum Finite Automata”. In: SOFSEM. Vol. 2540. LNCS. 2002, pp. 273–278.

[MP02] Carlo Mereghetti and Beatrice Palano. “On the Size of One-way Quantum Finite Automata with Periodic Behaviors”. In: Theoretical Informatics and Applications 36.3 (2002), pp. 277– 291.

[NIHK02] Masaki Nakanishi et al. “On the Power of Non-deterministic Quantum Finite Automata”. In: IEICE Transactions on Information and Systems E85-D.2 (2002), pp. 327–332.

[Ozo02] Raitis Ozols. “Deterministic Finite Automata and measure–many 1–way Quantum Finite Automata with non–isolated cutpoint”. In: Proceedings of International Workshop on Quantum Computation and Learning. 2002, pp. 47–50.

[Qiu02A] Daowen Qiu. “Characterization of sequential quantum machines”. In: International Journal of Theoretical Physics 41.5 (2002), pp. 811–822.

[Qiu02B] Daowen Qiu. “Quantum Pushdown Automata”. In: International Journal of Theoretical Physics 41.9 (2002), pp. 1627–1639.

[Ter02] Gints Tervits. “Probabilistic and Quantum Automata for Undecidability Proofs”. In: Proceedings of International Workshop on Quantum Computation and Learning. 2002, pp. 57– 61.

[YKI02] Tomohiro Yamasaki, Hirotada Kobayashi, and Hiroshi Imai. “Quantum versus Deterministic Counter Automata”. In: COCOON. Vol. 2387. LNCS. 2002, pp. 584–594.

[YKTI02] Tomohiro Yamasaki et al. “One-way probabilistic reversible and quantum one-counter automata”. In: Theoretical Computer Science 289.2 (2002), pp. 963–976.

2003: Edit

[ABB+03] Andris Ambainis et al. “Size of Quantum Versus Deterministic Finite Automata”. In: VLSI. CSREA Press, 2003, pp. 303–308.

[AK03] Andris Ambainis and Arnolds Ķikusts. “Exact results for accepting probabilities of quantum automata”. In: Theoretical Computer Science 295.1–3 (2003), pp. 3–25.

[BMP03A] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Quantum Computing: 1-Way Quantum Automata”. In: Developments in Language Theory. Vol. 2710. LNCS. 2003, pp. 1–20.

[BMP03B] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Lower Bounds on the Size of Quantum Automata Accepting Unary Languages”. In: ICTCS. Vol. 2841. 2003, pp. 86–96.

[BMP03C] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Golomb Rulers And Difference Sets For Succinct Quantum Automata”. In: International Journal of Foundations of Computer Science 14.5 (2003), pp. 871–888.

[BMP03D] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Approximating stochastic events by quantum automata”. In: ERATO International Conference on Quantum Information Science. Kyoto, Japan, 2003.

[Boz03] Symeon Bozapalidis. “Extending Stochastic and Quantum Functions”. In: Theory of Computing Systems 36.2 (2003), pp. 183–197.

2004: Edit

[ABGKMT04] Andris Ambainis et al. “Algebraic Results on Quantum Automata”. In: STACS. Vol. 2996. LNCS. 2004, pp. 93–104.

[Nak04] Masaki Nakanishi. “On the Power of One-Sided Error Quantum Pushdown Automata with Classical Stack Operations”. In: COCOON. Vol. 3106. LNCS. 2004, pp. 179–186.

[NY04] Harumichi Nishimura and Tomoyuki Yamakami. “An Application of Quantum Finite Automata to Interactive Proof Systems”. In: CIAA. Vol. 3317. LNCS. 2004, pp. 225–236.

[QY04] Daowen Qiu and Mingsheng Ying. “Characterizations of quantum automata”. In: Theoretical Computer Science 312.2-3 (2004), pp. 479–489. issn: 0304-3975.

2005: Edit

[AG05] Farid M. Ablayev and Aida Gainutdinova. “Complexity of Quantum Uniform and Nonuniform Automata”. In: Developments in Language Theory. Vol. 3572. LNCS. 2005, pp. 78– 87.

[BMP05A] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Small size quantum automata recognizing some regular languages”. In: Theoretical Computer Science 340.2 (2005), pp. 394–407.

[BMP05B] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Some formal methods for analyzing quantum automata”. In: DCFS. Universit`a degli Studi di Milano, Milan, Italy, 2005, pp. 1–14.

[BJKP05] Vincent D. Blondel et al. “Decidable and Undecidable Problems about Quantum Automata”. In: SIAM Journal on Computing 34.6 (2005), pp. 1464–1473.

[DJK05] Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. “Quantum automata and algebraic groups”. In: Journal of Symbolic Computation 39.3–4 (2005), pp. 357–371.

[Fre05] Rūsiņš Freivalds. “Languages Recognizable by Quantum Finite Automata”. In: CIAA. Vol. 3845. LNCS. 2005, pp. 1–14.

[Jea05] Emmanuel Jeandel. “Topological Automata”. In: STACS. Vol. 3404. LNCS. 2005, pp. 389–398.

[Kos05] Peter Košinár. “Konečné kvantové výpočtové modely”. (In Slovak). MA thesis. Bratislava, Slovakia: Faculty of Mathematics, Physics and Informatics, Comenius University, 2005.

[MNYW005] Yumiko Murakami et al. “Quantum versus Classical Pushdown Automata in Exact Computation”. In: IPSJ Digital Courier 1 (2005), pp. 426–435.

[Qiu05] Daowen Qiu. Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines. Tech. rep. arXiv:quant-ph/0501176. Presented in the Fourth Conference on Computability in Europe (CiE’2008), Athens, Greece, June 15- 20. 2005.

[RV05] M. V. Panduranga Rao and V. Vinay. “Quantum Finite Automata and Weighted Automata”. In: ACiD. Vol. 4. Texts in Algorithmics. (Technical Report: IISc-CSA-TR-2004-9 (http://www.csa.iisc.ernet.in/TR/2004/9/).) 2005, pp. 123–134.

[YKI05] Tomohiro Yamasaki, Hirotada Kobayashi, and Hiroshi Imai. “Quantum versus Deterministic Counter Automata”. In: Theoretical Computer Science 334.1-3 (2005), pp. 275–297.

2006: Edit

[ABGKMT06] Andris Ambainis et al. “Algebraic Results on Quantum Automata”. In: Theory of Computing Systems 39.1 (2006), pp. 165–188.

[BMP06] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Some formal tools for analyzing quantum automata”. In: Theoretical Computer Science 356.1 (2006), pp. 14–25.

[Gru06] Jozef Gruska. “Quantum Finite Automata”. In: Recent Advances in Formal Languages and Applications. Vol. 25. Studies in Computational Intelligence. Springer, 2006, pp. 81–117.

[LQ06] Lvzhou Li and Daowen Qiu. “Determination of equivalence between quantum sequential machines”. In: Theoretical Computer Science 358.1 (2006), pp. 65–74.

[Mac06] Martin Macko. On closure properties of quantum finite automata. Diploma thesis. Faculty of Mathematics, Physics and Informatics Comenius University, Bratislava. 2006.

[MP06A] Carlo Mereghetti and Beatrice Palano. “Quantum finite automata with control language”. In: Theoretical Informatics and Applications 40.2 (2006), pp. 315–332.

[MP06B] Carlo Mereghetti and Beatrice Palano. “Quantum Automata for some Multiperiodic Languages”. In: DCFS. New Mexico State University, 2006, pp. 199–210.

[NHK06] Masaki Nakanishi, Kiyoharu Hamaguchi, and Toshinobu Kashiwabara. “Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition”. In: IEICE Transactions 89-D.3 (2006), pp. 1120–1127.

2007: Edit

[AF07] Ruben Agadzanyan and Rūsiņš Freivalds. “Size of Quantum Finite State Transducers”. In: SOFSEM. Vol. 4362. LNCS. 2007, pp. 155–163.

[BRS07] Aleksandrs Belovs, Ansis Rosmanis, and Juris Smotrovs. “Multi-letter Reversible and Quantum Finite Automata”. In: Developments in Language Theory. Vol. 4588. LNCS. 2007, pp. 60–71.

[Hi07] Mika Hirvensalo. “Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages”. In: SOFSEM. Vol. 4362. LNCS. 2007, pp. 309–319.

[Jea07] Emmanuel Jeandel. “Topological Automata”. In: Theory of Computing Systems 40.4 (2007), pp. 397–407. issn: 1432-4350.

[Kud07] Manfred Kudlek. “Some Remarks on Quantum Automata”. In: International Journal of Foundations of Computer Science 18.6 (2007), pp. 1283–1292.

[Mer07] Mark Mercer. “Applications of Algebraic Automata Theory to Quantum Finite Automata”. PhD thesis. McGill University, 2007.

[MP07] Carlo Mereghetti and Beatrice Palano. “Quantum automata for some multiperiodic languages”. In: Theoretical Computer Science 387.2 (2007), pp. 177–186.

[Rao07] M. V. Panduranga Rao. “Bounds on Augmented Automata and Quantum Adiabatic Optimization”. PhD thesis. Indian Institute of Science, 2007.

[RV07] M. V. Panduranga Rao and V. Vinay. Quantum Finite Automata and Weighted Automata. Tech. rep. arXiv:quant-ph/0701144. 2007.

2008: Edit

[AN08] Andris Ambainis and Nikolajs Nahimovs. “Improved Constructions of Quantum Automata”. In: TQC. Vol. 5106. LNCS. 2008, pp. 47–56.

[Fre08] Rūsiņš Freivalds. “Super-exponential size advantage of quantum finite automata with mixed states”. In: ISAAC. Vol. 5369. LNCS. 2008, pp. 931–942.

[FB08] Rūsiņš Freivalds and Richard F. Bonner. “Quantum inductive inference by finite automata”. In: Theoretical Computer Science 397.1–3 (2008), pp. 70–76.

[Hi08] Mika Hirvensalo. “Various Aspects of Finite Quantum Automata”. In: Developments in Language Theory. Vol. 5257. LNCS. 2008, pp. 21–33.

[LQ08] Lvzhou Li and Daowen Qiu. “Determining the equivalence for one-way quantum finite automata”. In: Theoretical Computer Science 403.1 (2008), pp. 42–51.

[Mar08B] A. M. Martins. Dimension minimization of a quantum automaton. Tech. rep. arXiv:0807.0193. 2008.

[Mar08A] A. M. Martins. “Minimization of a quantum automaton: The transducer”. In: Physical Review A 78 (2008), pp. 062326 1–10.

[Mer08] Mark Mercer. “Lower Bounds for Generalized Quantum Finite Automata”. In: LATA. Vol. 5196. LNCS. 2008, pp. 373–384.

[Qiu08A] Daowen Qiu. Research report: State complexity of operations on two-way quantum finite automata. Tech. rep. arXiv:0807.0476. 2008.

[Qiu08B] Daowen Qiu. “Some Observations on Two-Way Finite Automata with Quantum and Classical States”. In: ICIC (1). Vol. 5226. LNCS. 2008, pp. 1–8.

[QL08] Daowen Qiu and Lvzhou Li. “An overview of quantum computation models: quantum automata”. In: Frontiers of Computer Science in China 2.2 (2008), pp. 193–207.

[Rao08] M. V. Panduranga Rao. “Interference automata”. In: Theoretical Computer Science 403.1 (2008).

[XWL08] Zhengjun Xi, Xin Wang, and Yongming Li. “Some algebraic properties of measure-once twoway quantum finite automata”. In: Quantum Information Processing 7.5 (2008), pp. 211–225.

2009: Edit

[AN09] Andris Ambainis and Nikolajs Nahimovs. “Improved constructions of quantum automata”. In: Theoretical Computer Science 410.20 (2009), pp. 1916–1922.

[BP09] Maria Paola Bianchi and Beatrice Palano. “Events and Languages on Unary Quantum Automata”. In: NCMA. Vol. 256. books@ocg.at. 2009, pp. 61–76.

[FOM09] Rūsiņš Freivalds, Māris Ozols, and Laura Mančinska. “Improved constructions of mixed state quantum automata”. In: Theoretical Computer Science 410.20 (2009), pp. 1923–1931.

[GKK09] Marats Golovkins, Maksim Kravtsev, and Vasilijs Kravcevs. “On a class of languages recognizable by probabilistic reversible decide-and-halt automata”. In: Theoretical Computer Science 410.20 (2009), pp. 1942–1951.

[LSF09] Lelde Lāce, Oksana Scegulnaja-Dubrovska, and Rūsiņš Freivalds. “Languages Recognizable by Quantum Finite Automata with cut-point 0”. In: SOFSEM. Vol. 2. 2009, pp. 35–46.

[LQ09] Lvzhou Li and Daowen Qiu. “A note on quantum sequential machines”. In: Theoretical Computer Science 410.26 (2009), pp. 2529–2535.

[NY09] Harumichi Nishimura and Tomoyuki Yamakami. “An application of quantum finite automata to interactive proof systems”. In: Journal of Computer and System Sciences 75.4 (2009), pp. 255–269.

[QS09] Daowen Qiu and Sheng Yu. “Hierarchy and equivalence of multi-letter quantum finite automata”. In: Theoretical Computer Science 410.30-32 (2009), pp. 3006–3017.

[YS09A] Abuzer Yakaryılmaz and A. C. Cem Say. Language Recognition by Generalized Quantum Finite Automata with Unbounded Error. Tech. rep. arXiv:0901.2703. 2009.

[YS09B] Abuzer Yakaryılmaz and A. C. Cem Say. “Efficient probability amplification in two-way quantum finite automata”. In: Theoretical Computer Science 410.20 (2009), pp. 1932–1941.

[YS09C] Abuzer Yakaryılmaz and A. C. Cem Say. “Languages recognized with unbounded error by quantum finite automata”. In: CSR. Vol. 5675. LNCS. 2009, pp. 356–367.

2010: Edit

[BMP10] Alberto Bertoni, Carlo Mereghetti, and Beatrice Palano. “Trace monoids with idempotent generators and measure-only quantum automata”. In: Natural Computing 9.2 (2010), pp. 383–395.

[BP10] Maria Paola Bianchi and Beatrice Palano. “Behaviours of Unary Quantum Automata”. In: Fundamenta Informaticae 104.1-2 (2010), pp. 1–15.

[Hi10] Mika Hirvensalo. “Quantum Automata with Open Time Evolution”. In: International Journal of Natural Computing 1.1 (2010), pp. 70–85.

[LQ10] Lvzhou Li and Daowen Qiu. “Revisiting the Power and Equivalence of One-Way Quantum Finite Automata”. In: ICIC (2). Vol. 6216. LNCS. 2010, pp. 1–8.

[Nak10] Masaki Nakanishi. “On the Weakness of One-Way Quantum Pushdown Automata”. In: Proceedings of the 2010 Fourth International Conference on Quantum, Nano and Micro Technologies. ICQNM’10. IEEE Computer Society, 2010, pp. 83–87.

[SY10A] A. C. Cem Say and Abuzer Yakaryılmaz. Quantum Function Computation Using Sublogarithmic Space. Tech. rep. arXiv:1009.3124. 2010.

[SYY10A] A. C. Cem Say, Abuzer Yakaryılmaz, and Şefika Yüzsever. “Quantum One-Way One-Counter Automata”. In: Randomized and Quantum Computation. Ed. by Rūsiņš Freivalds. 2010, pp. 25–34.

[SLF10] Oksana Scegulnaja-Dubrovska, Lelde Lāce, and Rūsiņš Freivalds. “Postselection finite quantum automata”. In: UC. Vol. 6079. LNCS. 2010, pp. 115–126.

[YS10A] Abuzer Yakaryılmaz and A. C. Cem Say. “Languages recognized by nondeterministic quantum finite automata”. In: Quantum Information and Computation 10.9&10 (2010), pp. 747– 770.

[YS10B] Abuzer Yakaryılmaz and A. C. Cem Say. “Succinctness of two-way probabilistic and quantum finite automata”. In: Discrete Mathematics and Theoretical Computer Science 12.4 (2010), pp. 19–40.

[YFSA10] Abuzer Yakaryılmaz et al. “Quantum Computation with Devices Whose Contents Are Never Read”. In: UC. Vol. 6079. LNCS. 2010, pp. 164–174.

2011: Edit

[AD11] Scott Aaronson and Andrew Drucker. “Advice Coins for Classical and Quantum Computation”. In: ICALP (1). Vol. 6755. LNCS. (arXiv:1101.5355). 2011, pp. 61–72.

[Amb11] Andris Ambainis. “Quantum Finite Automata”. In: NCMA. Vol. 282. books@ocg.at. 2011, pp. 9–13.

[GKK11] Marats Golovkins, Maksim Kravtsev, and Vasilijs Kravcevs. “Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages”. In: MFCS. Vol. 6907. LNCS. 2011, pp. 351–363.

[Hir11] Mika Hirvensalo. “Quantum Automata Theory – A Review”. In: Algebraic Foundations in Computer Science. Vol. 7020. LNCS. 2011, pp. 146–167.

[MP11] Carlo Mereghetti and Beatrice Palano. “Quantum Automata and Periodic Events”. In: Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory. Ed. by C. Martin-Vide. Vol. 2. Scientific Applications of Language Methods. London: Imperial College Press, 2011. Chap. Quantum Automata and Periodic Events, pp. 563–584.

[QMZ11] Daowen Qiu, Paulo Mateus, and Xiangfu Zou. One-way quantum finite automata together with classical states: Equivalence and Minimization. Tech. rep. arXiv:0909.1428. 2011.

[QLZMG11] Daowen Qiu et al. “Multi-letter quantum finite automata: decidability of the equivalence and minimization of states”. In: Acta Informatica 48.5-6 (2011), pp. 271–290.

[SY11A] A. C. Cem Say and Abuzer Yakarylmaz. “Computation with narrow CTCs”. In: UC. Vol. 6714. LNCS. 2011, pp. 201–211.

[Yak11A] Abuzer Yakaryılmaz. “Classical and Quantum Computation with Small Space Bounds”. (arXiv:1102.0378). PhD thesis. Bogazici University, 2011. arXiv

[Yak11B] Abuzer Yakaryılmaz. “Superiority of one-way and realtime quantum machines and new directions”. In: NCMA. 2011, pp. 209–224.

[YS11A] Abuzer Yakaryılmaz and A. C. Cem Say. “Unbounded-error Quantum Computation with Small Space Bounds”. In: Information and Computation 279.6 (2011), pp. 873–892.

[YS11B] Abuzer Yakaryılmaz and A. C. Cem Say. Probabilistic and quantum finite automata with postselection. Tech. rep. arXiv:1102.0666. (A preliminary version of this paper appeared in the Proceedings of Randomized and Quantum Computation (satellite workshop of MFCS and CSL 2010), pages 14-24, 2010.) 2011.

[YS11C] Abuzer Yakaryılmaz and A. C. Cem Say. NP has log-space verifiers with fixed-size public quantum registers. Tech. rep. arXiv:1101:5227. 2011.

[ZLQ11] Shenggen Zheng, Lvzhou Li, and Daowen Qiu. “Two-tape finite automata with quantum and classical states”. In: International Journal of Theoretical Physics 50.4 (2011), pp. 1262–1281.

2012: Edit

[AY12] Andris Ambainis and Abuzer Yakaryılmaz. “Superiority of exact quantum automata for promise problems”. In: Information Processing Letters 112.7 (2012), pp. 289–291.

[BNM12] Behera, C.K.; Nayak, T.; Meher, B., "Push down automata vs quantum push down automata," Advances in Engineering, Science and Management (ICAESM), 2012 International Conference on , vol., no., pp.188,191, 30-31 March 2012.

[CB12] Carlo Comin and Maria Paola Bianchi. Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata. Tech. rep. arXiv:1206.1702. 2012.

[DN12] Tirtharaj Dash and Tanistha Nayak. "Quantum Finite Automata: a Language Acceptor Model". International Journal of Advanced Research in Computer Science and Software Engineering, Vol 2, No 9, pp. 18-23, 2012. PDF

[Jub12] Brendan Juba. “On learning finite-state quantum sources”. In: Quantum Information & Computation 12.1–2 (2012), pp. 105–118.

[LF12] Lvzhou Li and Yuan Feng. On hybrid models of quantum finite automata. Tech. rep. arXiv:1206:2131, 2012.

[Lin12A] Tianrong Lin. On equivalence of multi-letter and multi-letter measure-many quantum finite automata. Tech. rep. arXiv:1203.0113. 2012.

[Lin12B] Tianrong Lin. “Another approach to the equivalence of measure-many one-way quantum finite automata and its application”. In: Journal of Computer and System Sciences 78.3 (2012). (Also check arXiv:1106.2481v10.), pp. 807–821.

[Lin12C] Tianrong Lin. Some results on equivalence of multi-letter quantum finite automata. Tech. rep. arXiv:1106.5223. 2011.

[LQZLWM12] Lvzhou Li et al. “Characterizations of one-way general quantum finite automata”. In: Theoretical Computer Science 419 (2012), pp. 73–91.

[MQL12] Paulo Mateus, Daowen Qiu, and Lvzhou Li. “On the complexity of minimizing probabilistic and quantum automata”. In: Information and Computation 218 (2012), pp. 36–53.

[QLMG12] Daowen Qiu et al. “Handbook on Finite State based Models and Applications”. In: ed. by Jiacun Wang. Discrete Mathematics and Its Applications. Chapman and Hall/CRC, 2012. Chap. Quantum finite automata.

[SY12B] A. C. Cem Say and Abuzer Yakarylmaz. “Computation with multiple CTCs of fixed length and width”. In: Natural Computing, Vol. 11, No. 4, pp. 579-594, 2012. (http://dx.doi.org/10.1007/s11047-012-9337-6).

[SY12A] A. C. Cem Say and Abuzer Yakarylmaz. “Quantum counter automata”. In: International Journal of Foundations of Computer Science 23.5 (2012), pp. 1099–1116.

[Yam12] Tomoyuki Yamakami. “One-Way Reversible and Quantum Finite Automata with Advice”. In: LATA. Vol. 7183. LNCS. (arXiv:1208.6092). 2012, pp. 526–537.

[Yak12A] Abuzer Yakaryılmaz. “Superiority of one-way and realtime quantum machines”. In: Theoretical Informatics and Applications, Vol. 46, No. 4, pp. 615–641, 2012. (http://dx.doi.org/10.1051/ita/2012018).

[Yak12B] Abuzer Yakaryılmaz. Turing-equivalent automata using a fixed-size quantum memory. Tech. rep. arXiv:1205.5395. 2012.

[YFSA12] Abuzer Yakaryılmaz et al. “Quantum Computation with write-only memory”. In: Natural Computing 11.1 (2012), pp. 81–94.

[ZQL12A] Shenggen Zheng, Daowen Qiu, and Lvzhou Li. State succinctness of two-way finite automata with quantum and classical states. Tech. rep. arXiv:1202.2651. 2012.

[ZQL12B] Shenggen Zheng, Daowen Qiu, and Lvzhou Li. “Some languages recognized by two-way finite automata with quantum and classical states”. In: International Journal of Foundations of Computer Science 23.5 (2012), pp. 1117–1129.

[ZQLG12] Shenggen Zheng et al. “One-way finite automata with quantum and classical states”. In: Languages Alive: Essays dedicated to Jrgen Dassow on the Occasion of His 65th Birthday. Ed. by Henning Bordihn, Martin Kutrib, and Bianca Truthe. Vol. 7300. LNCS Festschrift Series. 2012, pp. 273–290.

2013:Edit

[YS13A] Abuzer Yakaryılmaz and A. C. Cem Say. “Proving the power of postselection”. In: Fundamenta Informaticae, Vol. 123, No. 1, pp. 107-134, 2013. DOI arXiv correction

[Yak13A] Abuzer Yakaryilmaz, 2013. "Public qubits versus private coins". The prooceedings of Workshop on Quantum and Classical Complexity, pp. 45-60, 2013. (Univeristy of Latvia Press, ISBN: 978-9984-45-743-7) Proceedings ECCC

[Yak13B] Abuzer Yakaryilmaz. "One-counter verifiers for decidable languages". CSR2013: LNCS Vol. 7913, pp. 366-377, 2013 (Proceedings of the 8th International Computer Science Symposium in Russia). DOI ECCC arXiv

[Yak13C] Abuzer Yakaryilmaz. CSR2013: "Quantum alternation" LNCS Vol. 7913, pp. 334-346, 2013 (Proceedings of the 8th International Computer Science Symposium in Russia). DOI

2014:Edit

[AGKY14] Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, Abuzer Yakaryilmaz. "Very narrow quantum OBDDs and width hierarchies for classical OBDDs". DCFS2014: LNCC Vol. 8614, pp. 53-64, 2014 (16th International Workshop on Descriptional Complexity of Formal Systems). DOI arXiv

[AY14A] Aida Gainutdinova, Abuzer Yakaryilmaz. "Unary probabilistic and quantum automata on promise problems".

[BY14A] Marzio De Biasi, Abuzer Yakaryilmaz. "Unary languages recognized by two-way one-counter automata". CIAA2014: LNCC Vol. 8587, pp. 148-161, 2014 (19th International Conference on Implementation and Application of Automata). DOI arXiv

[Com14] Carlo Comin. "Algebraic Characterisation of the Class of Languages Recognised by Measure Only Quantum Automata". Fundamenta Informaticae, Vol. 134, 3-4, pp. 335-353, 2014. IOS arXiv

[DHRSY14] H. Gokalp Demirci, Mika Hirvensalo, Klaus Reinhardt, A. C. Cem Say, Abuzer Yakaryilmaz. "Classical and quantum realtime alternating automata". NCMA2014: books@ocg.at Vol. 304, pp. 101-114, 2014 (Sixth Workshop on Non-Classical Models for Automata and Applications). arXiv

[KY14A] Kamil Khadiev, Abuzer Yakaryilmaz. "New size hiearchies for two-way non-uniform automata". NCMA2014: Short paper appeared in a local prooceedings, pp. 13-18, 2014 (Sixth Workshop on Non-Classical Models for Automata and Applications).

[MY14A] Masaki Nakanishi, Abuzer Yakaryilmaz. " Classical and quantum counter automata on promise problems ". arXiv

[RY14A] Klaus Reinhardt, Abuzer Yakaryilmaz. "The minimum amount of useful space: New results and new directions". DLT2014:LNCC Vol. 8633, pp. 315-326, 2014 (Developments in Language Theory). DOI arXiv

[RY14B] Jibran Rashid, Abuzer Yakaryilmaz. "Implications of quantum automata for contextuality". CIAA2014: LNCC Vol. 8587, pp. 318-331, 2014 (19th International Conference on Implementation and Application of Automata). DOI arXiv

[SY14A] A.C.Cem Say, Abuzer Yakaryilmaz. "Quantum finite automata: A modern introduction". Computing with New Resources, LNCS Vol. 8008, pp. 208-222, 2014.arXiv

[SY14B] Arseny Shur, Abuzer Yakaryilmaz. "Quantum, Stochastic, and Pseudo Stochastic Languages with Few States".  UCNC2014: LNCC Vol. 8553, pp. 327-339, 2014 (13th International Conference on Unconventional Computation and Natural Computation). DOI Latest version: arXiv

[SY14C] A.C.Cem Say, Abuzer Yakaryilmaz, "Magic coins are useful for small-space quantum machines". ECCC

[YSD14] Abuzer Yakaryilmaz, A. C. Ce Say, H. Gokalp Demirci. "Debates with small transparent quantum verifiers". DLT2014: LNCC Vol. 8633, pp. 327-338, 2014 (Developments in Language Theory). DOI arXiv

[ZGQ14] S.G. Zheng,  J. Gruska and D.W. Qiu, On the state complexity of semi-quantum finite automata, RAIRO-Theoretical Informatics and Applications 48 (2014)  187-207.  Earlier version in LATA'14.

[GQZ14a] J. Gruska, D.W. Qiu, S.G. Zheng, Potential of quantum finite automata with exact acceptance, International Journal of Foundation of Computer Science, accepted, (2014). Also arXiv:1404.1689.

[GQZ14b] J. Gruska, D.W. Qiu and S.G. Zheng,  Generalizations of the distributed Deutsch-Jozsa promise problem,    arXiv:1402.7254 (2014).

[ZQ14] S.G. Zheng, D.W. Qiu, From quantum query complexity to state complexity, Gruska Festschrift, LNCS, 8808, pp. 231-245, (2014).

[LGZ14] J. Gruska, L.Z. Li, D.W. Qiu and S.G. Zheng, Recognizability versus solvability of promise problems in classical and quantum finite automata framework, arXiv:1411.3870.

Edit

2015:Edit

[GPA15] Giannakis, K., Papalitsas, C., & Andronikos, T. (2015, July). Quantum automata for infinite periodic words. In Information, Intelligence, Systems and Applications (IISA), 2015 6th International Conference on (pp. 1-6). IEEE.

[GPKSA15] Giannakis, K., Papalitsas, C., Kastampolidou, K., Singh, A., & Andronikos, T. (2015). Dominant Strategies of Quantum Games on Quantum Periodic Automata. Computation, 3(4), 586-599.

[GQZ15] Gruska, J., Qiu, D., & Zheng, S. (2015). Potential of quantum finite automata with exact acceptance. International Journal of Foundations of Computer Science, 26(03), 381-398.

[AY15] Ambainis, A., & Yakaryilmaz, A. (2015). Automata and quantum computing. arXiv preprint arXiv:1507.01988.

2016: Edit

[BMY16] Belovs, A., Montoya, J. A., & Yakaryılmaz, A. (2016, July). Looking for Pairs that Hard to Separate: A Quantum Approach. In International Conference on Implementation and Application of Automata (pp. 213-223). Springer International Publishing.

[BMP16] Bianchi, M. P., Mereghetti, C., & Palano, B. (2016). Quantum finite automata: Advances on Bertoni's ideas. Theoretical Computer Science.

[GR16] Ganguly, D., & Ray, K. S. (2016). 2-tape 1-way Quantum Finite State Automata. arXiv preprint arXiv:1607.00811.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.