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), p. 477-490 / Harvested from Numdam

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.

Publié le : 2001-01-01
Classification:  68Q10,  68Q19,  68Q45
@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},
     volume = {35},
     year = {2001},
     pages = {477-490},
     mrnumber = {1908867},
     zbl = {1010.68068},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 477-490. http://gdmltest.u-ga.fr/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 1615194

[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 1051.68062

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

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

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

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

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

[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 645539 | Zbl 0426.68001

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

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

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

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

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

[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 1050.68095

[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 0229.94033

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

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

[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 912712 | Zbl 0627.68069

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

[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 103795 | Zbl 0158.25404

[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 103796 | Zbl 0158.25601

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

[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 506094 | Zbl 0359.10041