spacer
EDP Sciences Journals List
Home arrow Document
Subscriber Authentication Point
   
Issue Theoret. Informatics Appl.
Volume 35, Number 5, September-October 2001
Page(s) 477 - 490
DOI 10.1051/ita:2001106

DOI: 10.1051/ita:2001106


Theoret. Informatics Appl. 35, 477-490 (2001)

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

Carlo Mereghetti1, Beatrice Palano2 and Giovanni Pighizzini3

1  Dipartimento di Informatica, Sist. e Com., Università degli Studi di Milano - Bicocca, via Bicocca degli Arcimboldi 8, 20126 Milano, Italy; mereghetti@disco.unimib.it.
2  Dipartimento di Informatica, Università degli Studi di Torino, c.so Svizzera 185, 10149 Torino, Italy; beatrice@di.unito.it.
3  Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy; pighizzi@dsi.unimi.it.

(Received December 13, 2001. Accepted March 15, 2002.)

Abstract
We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\mbox\}$ }$ of cyclic languages, where $L_m={\{{a^{km}} \;\vert\;{k\in {\mbox{\rm\bf 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.


Mathematics Subject Classification. 68Q10, 68Q19, 68Q45

Key words: Deterministic -- nondeterministic -- probabilistic -- quantum unary finite automata.


© EDP Sciences 2001


What is OpenURL?