Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata

Mereghetti, Carlo; Palano, Beatrice; Pighizzini, Giovanni

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 $\left\{L_m\right\}$ of cyclic languages, where $L_m=\left\{a^{km}\right|k\in \mathbb{N}\}$. 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^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_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.

[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