We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family of cyclic languages, where . In particular, we show that, for any , the number of states necessary and sufficient for accepting the unary language with isolated cut point on one-way probabilistic finite automata is , with being the factorization of . 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 , accept 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.
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://www.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://www.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://www.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://www.numdam.org/item/ITA_2001__35_5_477_0/
[1] 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]
& , 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] Characterizations of 1-way quantum finite automata, Techn. Rep. 99-03. Univ. of British Columbia, Dept. of Computer Science (1999). | Zbl
& ,[4] Alternation. J. ACM 28 (1981) 114-133. | MR | Zbl
, & ,[5] Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-158. | MR | Zbl
,[6] Applications of Theory of Matrices. Interscience Pub., New York (1959). | MR | Zbl
,[7] Quantum Computing. McGraw-Hill, London, New York (1999). | MR
,[8] Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb 5 (2000) 191-218. | MR | Zbl
,[9] 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] Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979). | MR | Zbl
& ,[11] Alternating pushdown and stack automata. SIAM J. Comput. 13 (1984) 135-155. | MR | Zbl
, & ,[12] Uber die Maximalordung der Permutationen gegebenen Grades. Archiv. der Math. und Phys. 3 (1903) 92-103. | JFM
,[13] Handbuch der lehre von der verteilung der primzahlen. I. Teubner, Leipzig, Berlin (1909). | JFM
,[14] Two-Way automata simulations and unary languages. J. Autom. Lang. Comb. 5 (2000) 287-300. | MR | Zbl
& ,[15] Optimal simulations between unary autom. SIAM J. Comput. 30 (2001) 1976-1992. | MR | Zbl
& ,[16] 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] 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] 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] Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | MR | Zbl
& ,[20] Introduction to Probabilistic Automata. Academic Press, New York, London (1971). | MR | Zbl
,[21] 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] Probabilistic automata. Inform. and Control 6 (1963) 230-245. | Zbl
,[23] 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] 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] On the maximal order in and . Acta Arithmetica 37 (1980) 321-331. | MR | Zbl
,[26] Combinatorics, partitions, group theory, edited by B. Serge, Colloquio Internazionale sulle Teorie Combinatorie. Acc. Naz. dei Lincei, Rome (1976) 181-200. | MR | Zbl
,