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

¹ 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: 13 December 2001
Accepted: 15 March 2002

Abstract

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