Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 477-490.

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {L m } of cyclic languages, where L m ={a km |k}. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language L m with isolated cut point on one-way probabilistic finite automata is p 1 α 1 +p 2 α 2 ++p s α s , with p 1 α 1 p 2 α 2 p s α s being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages with isolated cut point on the one-way probabilistic model. Moreover, we exhibit one-way quantum finite automata that, for any m, accept L m with isolated cut point and only two states. These results are settled within a survey on unary automata aiming to compare the descriptional power of deterministic, nondeterministic, probabilistic and quantum paradigms.

Classification : 68Q10, 68Q19, 68Q45
Mots clés : deterministic, nondeterministic, probabilistic, quantum unary finite automata
@article{ITA_2001__35_5_477_0,
     author = {Mereghetti, Carlo and Palano, Beatrice and Pighizzini, Giovanni},
     title = {Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {477--490},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {5},
     year = {2001},
     mrnumber = {1908867},
     zbl = {1010.68068},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2001__35_5_477_0/}
}
TY  - JOUR
AU  - Mereghetti, Carlo
AU  - Palano, Beatrice
AU  - Pighizzini, Giovanni
TI  - Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 477
EP  - 490
VL  - 35
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_5_477_0/
LA  - en
ID  - ITA_2001__35_5_477_0
ER  - 
%0 Journal Article
%A Mereghetti, Carlo
%A Palano, Beatrice
%A Pighizzini, Giovanni
%T Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 477-490
%V 35
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2001__35_5_477_0/
%G en
%F ITA_2001__35_5_477_0
Mereghetti, Carlo; Palano, Beatrice; Pighizzini, Giovanni. Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 477-490. http://archive.numdam.org/item/ITA_2001__35_5_477_0/

[1] A. Ambainis, The complexity of probabilistic versus deterministic finite automata, in Proc. 7th International Symposium on Algorithms and Computation (ISAAC). Springer, Lecture Notes in Comput. Sci. 1178 (1996) 233-238. | MR

[2] A. Ambainis&R. Freivalds, 1-way quantum finite automata: Strengths, weaknesses and generalizations, in Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press (1998) 332-342.

[3] A. Brodsky&N. Pippenger, Characterizations of 1-way quantum finite automata, Techn. Rep. 99-03. Univ. of British Columbia, Dept. of Computer Science (1999). | Zbl

[4] A. Chandra, D. Kozen&L. Stockmeyer, Alternation. J. ACM 28 (1981) 114-133. | MR | Zbl

[5] M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-158. | MR | Zbl

[6] F. Gantmacher, Applications of Theory of Matrices. Interscience Pub., New York (1959). | MR | Zbl

[7] J. Gruska, Quantum Computing. McGraw-Hill, London, New York (1999). | MR

[8] J. Gruska, Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb 5 (2000) 191-218. | MR | Zbl

[9] A. Kondacs&J. Watrous, On the power of quantum finite state automata, in Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press (1997) 66-75.

[10] J. Hopcroft&J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979). | MR | Zbl

[11] R. Ladner, R. Lipton &L. Stockmeyer, Alternating pushdown and stack automata. SIAM J. Comput. 13 (1984) 135-155. | MR | Zbl

[12] E. Landau, Uber die Maximalordung der Permutationen gegebenen Grades. Archiv. der Math. und Phys. 3 (1903) 92-103. | JFM

[13] E. Landau, Handbuch der lehre von der verteilung der primzahlen. I. Teubner, Leipzig, Berlin (1909). | JFM

[14] C. Mereghetti&G. Pighizzini, Two-Way automata simulations and unary languages. J. Autom. Lang. Comb. 5 (2000) 287-300. | MR | Zbl

[15] C. Mereghetti&G. Pighizzini, Optimal simulations between unary autom. SIAM J. Comput. 30 (2001) 1976-1992. | MR | Zbl

[16] A. Meyer&M. Fischer, Economy of description by automata, grammars, and formal systems, in Proc. 12th Annual Symposium on Switching and Automata Theory. East Lansing, Michigan (1971) 188-191.

[17] M. Milani&G. Pighizzini, Tight bounds on the simulation of unary probabilistic automata by deterministic automata, in Pre-Proc. Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS), Techn. Rep. 555. Univ. of Western Ontario, Canada, Dept. Comp. Sci., J. Autom. Lang. and Comb. (2000). | Zbl

[18] E. Moore, On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. C-20 (1971) 1211-1214. | Zbl

[19] C. Moore&J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | MR | Zbl

[20] A. Paz, Introduction to Probabilistic Automata. Academic Press, New York, London (1971). | MR | Zbl

[21] J.E. Pin, On Languages Accepted by finite reversible automata, in Proc. of the 14th International Colloquium on Automata, Languages and Programming (ICALP). Springer-Verlag, Lecture Notes in Comput. Sci. 267 (1987) 237-249. | MR | Zbl

[22] M. Rabin, Probabilistic automata. Inform. and Control 6 (1963) 230-245. | Zbl

[23] M. Rabin&D. Scott, Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-125. Also in: E.F. Moore, Sequential Machines: Selected Papers. Addison-Wesley, Reading, MA (1964). | MR | Zbl

[24] J. Shepherdson, The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3 (1959) 198-200. Also in: E.F. Moore, Sequential Machines: Selected Papers. Addison-Wesley, Reading, MA (1964). | MR | Zbl

[25] M. Szalay, On the maximal order in S n and S n * . Acta Arithmetica 37 (1980) 321-331. | MR | Zbl

[26] P. Turán, Combinatorics, partitions, group theory, edited by B. Serge, Colloquio Internazionale sulle Teorie Combinatorie. Acc. Naz. dei Lincei, Rome (1976) 181-200. | MR | Zbl