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

Mereghetti, Carlo; Palano, Beatrice; Pighizzini, Giovanni

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

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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^{k m} | k \in ℕ}$ . 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}} + \dots + p_{s}^{α_{s}}$ , with $p_{1}^{α_{1}} p_{2}^{α_{2}} \dots 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

MR 1908867 | Zbl 1010.68068 | 4 citations dans Numdam

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/

Bibliographie

[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