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

Issue		RAIRO-Theor. Inf. 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 Mereghetti¹, Beatrice Palano² and Giovanni Pighizzini³

¹ Dipartimento di Informatica, Sist. e Com., Università degli Studi di Milano - Bicocca, via Bicocca degli Arcimboldi 8, 20126 Milano, Italy; mereghetti@disco.unimib.it.
² Dipartimento di Informatica, Università degli Studi di Torino, c.so Svizzera 185, 10149 Torino, Italy; beatrice@di.unito.it.
³ 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{$\{{L_m}\}$ }$ 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 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.

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

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

© EDP Sciences 2001

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.