×

Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata. (English) Zbl 1010.68068

Summary: 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} \mid 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_s}+\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.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q19 Descriptive complexity and finite models
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Numdam Numdam EuDML

References:

[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 · Zbl 1036.68510
[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 · Zbl 1051.68062 · doi:10.1137/S0097539799353443
[4] A. Chandra , D. Kozen & L. Stockmeyer , Alternation . J. ACM 28 ( 1981 ) 114 - 133 . MR 603186 | Zbl 0473.68043 · Zbl 0473.68043 · doi:10.1145/322234.322243
[5] M. Chrobak , Finite automata and unary languages . Theoret. Comput. Sci. 47 ( 1986 ) 149 - 158 . MR 881208 | Zbl 0638.68096 · Zbl 0638.68096 · doi:10.1016/0304-3975(86)90142-8
[6] F. Gantmacher , Applications of Theory of Matrices . Interscience Pub., New York ( 1959 ). MR 107648 | Zbl 0085.01001 · 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 · 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 · 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 · Zbl 0538.68039 · doi:10.1137/0213010
[12] E. Landau , Uber die Maximalordung der Permutationen gegebenen Grades . Archiv. der Math. und Phys. 3 ( 1903 ) 92 - 103 . JFM 34.0233.02 · JFM 34.0233.02
[13] E. Landau , Handbuch der lehre von der verteilung der primzahlen . I. Teubner, Leipzig, Berlin ( 1909 ). JFM 40.0232.08 · 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 · 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 · Zbl 0980.68048 · doi:10.1137/S009753979935431X
[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 · 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 · Zbl 0229.94033 · doi:10.1109/T-C.1971.223108
[19] C. Moore & J. Crutchfield , Quantum automata and quantum grammars . Theoret. Comput. Sci. 237 ( 2000 ) 275 - 306 . MR 1756213 | Zbl 0939.68037 · Zbl 0939.68037 · doi:10.1016/S0304-3975(98)00191-1
[20] A. Paz , Introduction to Probabilistic Automata . Academic Press, New York, London ( 1971 ). MR 289222 | Zbl 0234.94055 · 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 · Zbl 0627.68069
[22] M. Rabin , Probabilistic automata . Inform. and Control 6 ( 1963 ) 230 - 245 . Zbl 0182.33602 · Zbl 0182.33602 · doi:10.1016/S0019-9958(63)90290-0
[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 · 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 · Zbl 0158.25601
[25] M. Szalay , On the maximal order in \(S_n\) and \(S^*_n\) . Acta Arithmetica 37 ( 1980 ) 321 - 331 . Article | MR 598884 | Zbl 0443.10029 · 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 · Zbl 0359.10041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.