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.  Zbl1036.68510
  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.  Zbl0638.68096
  6. F. Gantmacher, Applications of Theory of Matrices. Interscience Pub., New York (1959).  Zbl0085.01001
  7. J. Gruska, Quantum Computing. McGraw-Hill, London, New York (1999).  Zbl0985.81022
  8. J. Gruska, Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb5 (2000) 191-218.  Zbl0965.68021
  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.  Zbl0538.68039
  12. E. Landau, Uber die Maximalordung der Permutationen gegebenen Grades. Archiv. der Math. und Phys.3 (1903) 92-103.  Zbl34.0233.02
  13. E. Landau, Handbuch der lehre von der verteilung der primzahlen. I. Teubner, Leipzig, Berlin (1909).  Zbl40.0232.09
  14. C. Mereghettiand G. Pighizzini, Two-Way automata simulations and unary languages. J. Autom. Lang. Comb.5 (2000) 287-300.  Zbl0965.68043
  15. C. Mereghettiand G. Pighizzini, Optimal simulations between unary autom. SIAM J. Comput.30 (2001) 1976-1992.  Zbl0980.68048
  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.  Zbl0229.94033
  19. C. Mooreand J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275-306.  Zbl0939.68037
  20. A. Paz, Introduction to Probabilistic Automata. Academic Press, New York, London (1971).  Zbl0234.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.  Zbl0627.68069
  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.  Zbl0443.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.  

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.