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

Mereghetti, Carlo ; Palano, Beatrice ; Pighizzini, Giovanni 

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 477-490

Résumé

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

Détail

Classification : 68Q10, 68Q19, 68Q45
Keywords: deterministic, nondeterministic, probabilistic, quantum unary finite automata