F. Ablayev, A. Gainutdinova, K. Khadiev, and A. Yakary?lmaz, Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs, Descriptional Complexity of Formal Systems, pp.53-64, 2014.
DOI : 10.1007/978-3-319-09704-6_6

A. Ambainis and A. Yakary?lmaz, Superiority of exact quantum automata for promise problems, Information Processing Letters, vol.112, issue.7, pp.289-291, 2012.
DOI : 10.1016/j.ipl.2012.01.001

Z. Bednárová, V. Geffert, K. Reinhardt, and A. Yakary?lmaz, New Results on the Minimum Amount of Useful Space, International Journal of Foundations of Computer Science, vol.27, issue.02, 1405.
DOI : 10.1142/S0129054116400098

M. P. Bianchi, C. Mereghetti, and B. Palano, Complexity of Promise Problems on Classical and Quantum Automata, Gruska Festschrift, pp.161-175, 2014.
DOI : 10.1007/978-3-319-13350-8_12

R. G. Bukharaev, Probabilistic automata, Journal of Soviet Mathematics, vol.18, issue.No. 2, pp.359-386, 1980.
DOI : 10.1007/BF01088986

R. Chang, J. Hartmanis, and D. Ranjan, Space bounded computations: Review and new separation results, Theoretical Computer Science, vol.80, pp.289-302, 1991.

A. Condon and R. J. Lipton, On the complexity of space bounded interactive proofs (extended abstract), Proc. Foundations of Computer Science, pp.462-467, 1989.

P. Pavol?duri?, J. Hromkovi?, D. P. José, G. Rolim, and . Schnitger, Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations, Symposium on Theoretical Aspects of Computer Science, pp.117-128, 1997.

C. Dwork and L. Stockmeyer, Finite state verifiers I: the power of interaction, Journal of the ACM, vol.39, issue.4, pp.800-828, 1992.
DOI : 10.1145/146585.146599

C. Dwork and L. J. Stockmeyer, A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata, SIAM Journal on Computing, vol.19, issue.6, pp.1011-1123, 1990.
DOI : 10.1137/0219069

A. Gainutdinova and A. Yakary?lmaz, Unary Probabilistic and Quantum Automata on Promise Problems, Developments in Language Theory, pp.252-263, 2015.
DOI : 10.1007/978-3-319-21500-6_20

V. Geffert, Nondeterministic Computations in Sublogarithmic Space and Space Constructibility, SIAM Journal on Computing, vol.20, issue.3, pp.484-498, 1991.
DOI : 10.1137/0220031

V. Geffert, An alternating hierarchy for finite automata, Theoretical Computer Science, vol.445, pp.1-24, 2012.
DOI : 10.1016/j.tcs.2012.04.044

V. Geffert and A. Okhotin, Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata, In Mathematical Foundations of Computer Science, Part I Lecture Notes in Computer Science, vol.8634, pp.291-302, 2014.
DOI : 10.1007/978-3-662-44522-8_25

V. Geffert and A. Yakary?lmaz, Classical Automata on Promise Problems, Descriptional Complexity of Formal Systems, pp.126-137
DOI : 10.1007/978-3-319-09704-6_12
URL : https://hal.archives-ouvertes.fr/hal-01349053

O. Goldreich, On Promise Problems: A Survey, Essays in Memory of Shimon Even, pp.254-290, 2006.
DOI : 10.1007/11685654_12

J. Gruska, L. Li, and S. Zheng, Recognizability versus solvability of promise problems in finite classical and quantum automata framework, Computing Research Repository, 1411.

J. Gruska, D. Qiu, and S. Zheng, Generalizations of the distributed Deutsch???Jozsa promise problem, Mathematical Structures in Computer Science, vol.12, issue.03
DOI : 10.1016/j.tcs.2013.06.005

J. Gruska, D. Qiu, and S. Zheng, Potential of Quantum Finite Automata with Exact Acceptance, International Journal of Foundations of Computer Science, vol.26, issue.03, pp.381-398, 2015.
DOI : 10.1142/S0129054115500215

J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages , and Computation, 2007.

J. Hromkovi?, Design and Analysis of Randomized Algorithms (Introduction to Design Paradigms), 2005.

J. Hromkovi? and G. Schnitger, On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata, Information and Computation, vol.169, issue.2, pp.284-296, 2001.
DOI : 10.1006/inco.2001.3040

G. Jirásková and G. Pighizzini, Optimal simulation of self-verifying automata by deterministic automata, Information and Computation, vol.209, issue.3, pp.528-535, 2011.
DOI : 10.1016/j.ic.2010.11.017

C. A. Kapoutsis, Removing Bidirectionality from Nondeterministic Finite Automata, In Mathematical Foundations of Computer Science Lecture Notes in Computer Science, vol.3618, pp.544-555, 2005.
DOI : 10.1007/11549345_47

C. A. Kapoutsis, R. Královi?, and T. Mömke, Size complexity of rotating and sweeping automata, Journal of Computer and System Sciences, vol.78, issue.2, pp.537-558, 2012.
DOI : 10.1016/j.jcss.2011.06.004

Y. I. Kuklin, Two-way probabilistic automata. Avtomatika i vy?istitel 'naja tekhnika, pp.35-36, 1973.

R. Kumar, Theory of Automata, Languages, and Computation, 2010.

R. E. Ladner, R. J. Lipton, and L. J. Stockmeyer, Alternating Pushdown and Stack Automata, SIAM Journal on Computing, vol.13, issue.1, pp.135-155, 1984.
DOI : 10.1137/0213010

C. Mereghetti and G. Pighizzini, Optimal Simulations between Unary Automata, SIAM Journal on Computing, vol.30, issue.6, pp.1976-1992, 2001.
DOI : 10.1137/S009753979935431X

Y. Murakami, M. Nakanishi, S. Yamashita, and K. Watanabe, Quantum versus Classical Pushdown Automata in Exact Computation, IPSJ Digital Courier, vol.1, pp.426-435, 2005.
DOI : 10.2197/ipsjdc.1.426

M. Nakanishi, Quantum Pushdown Automata with a Garbage Tape, In SOFSEM: Theory and Practice of Computer Science Lecture Notes in Computer Science, vol.8939, pp.352-363
DOI : 10.1007/978-3-662-46078-8_29

M. Nakanishi and A. Yakary?lmaz, Classical and Quantum Counter Automata on Promise Problems, Conference on Implementation and Application of Automata, pp.224-237, 2015.
DOI : 10.1007/978-3-319-22360-5_19

A. Paz, Introduction to Probabilistic Automata, 1971.

J. Rashid and A. Yakary?lmaz, Implications of Quantum Automata for Contextuality, Lecture Notes in Computer Science, vol.8587, pp.318-331, 2014.
DOI : 10.1007/978-3-319-08846-4_24

K. Reinhardt and A. Yakary?lmaz, The Minimum Amount of Useful Space: New Results and New Directions, Developments in Language Theory, pp.315-326, 2014.
DOI : 10.1007/978-3-319-09698-8_28

M. Sipser, Lower bounds on the size of sweeping automata, Journal of Computer and System Sciences, vol.21, issue.2, pp.195-202, 1980.
DOI : 10.1016/0022-0000(80)90034-3

R. Edwin-stearns, J. Hartmanis, P. M. Lewis, and I. , Hierarchies of memory limited computations, 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965), pp.179-190, 1965.
DOI : 10.1109/FOCS.1965.11

J. Watrous, Quantum computational complexity, Encyclopedia of Complexity and Systems Science, pp.7174-7201, 2009.

A. Yakary?lmaz and A. C. Say, Succinctness of two-way probabilistic and quantum finite automata, Discrete Mathematics and Theoretical Computer Science, vol.12, issue.2, pp.19-40, 2010.

S. Zheng, J. Gruska, and D. Qiu, On the State Complexity of Semi-quantum Finite Automata, Language and Automata Theory and Applications, pp.601-612, 2014.
DOI : 10.1007/978-3-319-04921-2_49

S. Zheng, D. Qiu, J. Gruska, L. Li, and P. Mateus, State succinctness of two-way finite automata with quantum and classical states, Theoretical Computer Science, vol.499, pp.98-112, 2013.
DOI : 10.1016/j.tcs.2013.06.005