Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

Carlo Mereghetti; Beatrice Palano; Giovanni Pighizzini

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 {Lm} of cyclic languages, where Lm = akm | k ∈ N. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm 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 Lm 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 35.5 (2010): 477-490. <http://eudml.org/doc/222058>.

@article{Mereghetti2010,
abstract = { We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family \{Lm\} of cyclic languages, where Lm = akm | k ∈ N. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm 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 Lm 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},
keywords = {Deterministic; nondeterministic; probabilistic; quantum unary finite automata.; unary automata; cyclic languages},
language = {eng},
month = {3},
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/222058},
volume = {35},
year = {2010},
}

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
DA - 2010/3//
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 {Lm} of cyclic languages, where Lm = akm | k ∈ N. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm 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 Lm 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/222058
ER -

References

top
  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.  
  2. A. Ambainisand 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. Brodskyand N. Pippenger, Characterizations of 1-way quantum finite automata, Techn. Rep. 99-03. Univ. of British Columbia, Dept. of Computer Science (1999).  
  4. A. Chandra, D. Kozenand L. Stockmeyer, Alternation. J. ACM28 (1981) 114-133.  
  5. M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci.47 (1986) 149-158.  
  6. F. Gantmacher, Applications of Theory of Matrices. Interscience Pub., New York (1959).  
  7. J. Gruska, Quantum Computing. McGraw-Hill, London, New York (1999).  
  8. J. Gruska, Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb5 (2000) 191-218.  
  9. A. Kondacsand 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. Hopcroftand J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979).  
  11. R. Ladner, R. Lipton and L. Stockmeyer, Alternating pushdown and stack automata. SIAM J. Comput.13 (1984) 135-155.  
  12. E. Landau, Uber die Maximalordung der Permutationen gegebenen Grades. Archiv. der Math. und Phys.3 (1903) 92-103.  
  13. E. Landau, Handbuch der lehre von der verteilung der primzahlen. I. Teubner, Leipzig, Berlin (1909).  
  14. C. Mereghettiand G. Pighizzini, Two-Way automata simulations and unary languages. J. Autom. Lang. Comb.5 (2000) 287-300.  
  15. C. Mereghettiand G. Pighizzini, Optimal simulations between unary autom. SIAM J. Comput.30 (2001) 1976-1992.  
  16. A. Meyerand 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. Milaniand 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).  
  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.  
  19. C. Mooreand J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275-306.  
  20. A. Paz, Introduction to Probabilistic Automata. Academic Press, New York, London (1971).  
  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.  
  22. M. Rabin, Probabilistic automata. Inform. and Control6 (1963) 230-245.  
  23. M. Rabinand 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).  
  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).  
  25. M. Szalay, On the maximal order in Sn and S*n. Acta Arithmetica37 (1980) 321-331.  
  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.  

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.