# 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

## Access Full Article

top## Abstract

top## How to cite

topMereghetti, 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- 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
- 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.
- A. Brodskyand N. Pippenger, Characterizations of 1-way quantum finite automata, Techn. Rep. 99-03. Univ. of British Columbia, Dept. of Computer Science (1999).
- A. Chandra, D. Kozenand L. Stockmeyer, Alternation. J. ACM28 (1981) 114-133.
- M. Chrobak, Finite automata and unary languages. Theoret. Comput. Sci.47 (1986) 149-158. Zbl0638.68096
- F. Gantmacher, Applications of Theory of Matrices. Interscience Pub., New York (1959). Zbl0085.01001
- J. Gruska, Quantum Computing. McGraw-Hill, London, New York (1999). Zbl0985.81022
- J. Gruska, Descriptional complexity issues in quantum computing. J. Autom. Lang. Comb5 (2000) 191-218. Zbl0965.68021
- 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.
- J. Hopcroftand J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979).
- R. Ladner, R. Lipton and L. Stockmeyer, Alternating pushdown and stack automata. SIAM J. Comput.13 (1984) 135-155. Zbl0538.68039
- E. Landau, Uber die Maximalordung der Permutationen gegebenen Grades. Archiv. der Math. und Phys.3 (1903) 92-103. Zbl34.0233.02
- E. Landau, Handbuch der lehre von der verteilung der primzahlen. I. Teubner, Leipzig, Berlin (1909). Zbl40.0232.09
- C. Mereghettiand G. Pighizzini, Two-Way automata simulations and unary languages. J. Autom. Lang. Comb.5 (2000) 287-300. Zbl0965.68043
- C. Mereghettiand G. Pighizzini, Optimal simulations between unary autom. SIAM J. Comput.30 (2001) 1976-1992. Zbl0980.68048
- 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.
- 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).
- 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
- C. Mooreand J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275-306. Zbl0939.68037
- A. Paz, Introduction to Probabilistic Automata. Academic Press, New York, London (1971). Zbl0234.94055
- 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
- M. Rabin, Probabilistic automata. Inform. and Control6 (1963) 230-245.
- 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).
- 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).
- M. Szalay, On the maximal order in Sn and S*n. Acta Arithmetica37 (1980) 321-331. Zbl0443.10029
- P. Turán, Combinatorics, partitions, group theory, edited by B. Serge, Colloquio Internazionale sulle Teorie Combinatorie. Acc. Naz. dei Lincei, Rome (1976) 181-200.

## Citations in EuDML Documents

top- Maria Paola Bianchi, Giovanni Pighizzini, Normal forms for unary probabilistic automata
- Maria Paola Bianchi, Giovanni Pighizzini, Normal forms for unary probabilistic automata
- Maria Paola Bianchi, Giovanni Pighizzini, Normal forms for unary probabilistic automata
- Shenggen Zheng, Jozef Gruska, Daowen Qiu, On the state complexity of semi-quantum finite automata
- Carlo Mereghetti, Beatrice Palano, Quantum finite automata with control language

## NotesEmbed ?

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