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

Carlo Mereghetti; Beatrice Palano; Giovanni Pighizzini

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • Volume: 35, Issue: 5, page 477-490
  • ISSN: 0988-3754

Abstract

top
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 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.

How to cite

top

Mereghetti, Carlo, Palano, Beatrice, and Pighizzini, Giovanni. "Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.5 (2001): 477-490. <http://eudml.org/doc/92678>.

@article{Mereghetti2001,
abstract = {We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\lbrace \{L_m\}\rbrace $ of cyclic languages, where $L_m=\{\lbrace \{a^\{km\}\} \;|\;\{k\in \mathbb \{N\}\}\rbrace \}$. 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.},
author = {Mereghetti, Carlo, Palano, Beatrice, Pighizzini, Giovanni},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {deterministic; nondeterministic; probabilistic; quantum unary finite automata; unary automata; cyclic languages},
language = {eng},
number = {5},
pages = {477-490},
publisher = {EDP-Sciences},
title = {Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata},
url = {http://eudml.org/doc/92678},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 5
SP - 477
EP - 490
AB - We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\lbrace {L_m}\rbrace $ of cyclic languages, where $L_m={\lbrace {a^{km}} \;|\;{k\in \mathbb {N}}\rbrace }$. 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.
LA - eng
KW - deterministic; nondeterministic; probabilistic; quantum unary finite automata; unary automata; cyclic languages
UR - http://eudml.org/doc/92678
ER -

References

top
  1. [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. Zbl1036.68510MR1615194
  2. [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. [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). Zbl1051.68062
  4. [4] A. Chandra, D. Kozen& L. Stockmeyer, Alternation. J. ACM 28 (1981) 114-133. Zbl0473.68043MR603186
  5. [5] M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-158. Zbl0638.68096MR881208
  6. [6] F. Gantmacher, Applications of Theory of Matrices. Interscience Pub., New York (1959). Zbl0085.01001MR107648
  7. [7] J. Gruska, Quantum Computing. McGraw-Hill, London, New York (1999). MR1978991
  8. [8] J. Gruska, Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb 5 (2000) 191-218. Zbl0965.68021MR1778471
  9. [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. [10] J. Hopcroft& J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979). Zbl0426.68001MR645539
  11. [11] R. Ladner, R. Lipton & L. Stockmeyer, Alternating pushdown and stack automata. SIAM J. Comput. 13 (1984) 135-155. Zbl0538.68039MR731032
  12. [12] E. Landau, Uber die Maximalordung der Permutationen gegebenen Grades. Archiv. der Math. und Phys. 3 (1903) 92-103. Zbl34.0233.02JFM34.0233.02
  13. [13] E. Landau, Handbuch der lehre von der verteilung der primzahlen. I. Teubner, Leipzig, Berlin (1909). Zbl40.0232.08JFM40.0232.08
  14. [14] C. Mereghetti& G. Pighizzini, Two-Way automata simulations and unary languages. J. Autom. Lang. Comb. 5 (2000) 287-300. Zbl0965.68043MR1778478
  15. [15] C. Mereghetti& G. Pighizzini, Optimal simulations between unary autom. SIAM J. Comput. 30 (2001) 1976-1992. Zbl0980.68048MR1856565
  16. [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. [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). Zbl1050.68095
  18. [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. Zbl0229.94033
  19. [19] C. Moore& J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. Zbl0939.68037MR1756213
  20. [20] A. Paz, Introduction to Probabilistic Automata. Academic Press, New York, London (1971). Zbl0234.94055MR289222
  21. [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. Zbl0627.68069MR912712
  22. [22] M. Rabin, Probabilistic automata. Inform. and Control 6 (1963) 230-245. Zbl0182.33602
  23. [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). Zbl0158.25404MR103795
  24. [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). Zbl0158.25601MR103796
  25. [25] M. Szalay, On the maximal order in S n and S n * . Acta Arithmetica 37 (1980) 321-331. Zbl0443.10029MR598884
  26. [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. Zbl0359.10041MR506094

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.