RAIRO - Theoretical Informatics and Applications

Table of Contents - September 2001 - Volume 35, Issue 05  

Research Article

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

Mereghetti, Carloa1, Palano, Beatricea2 and Pighizzini, Giovannia3

a1 Dipartimento di Informatica, Sist. e Com., Università degli Studi di Milano – Bicocca, via Bicocca degli Arcimboldi 8, 20126 Milano, Italy; mereghetti@disco.unimib.it.

a2 Dipartimento di Informatica, Università degli Studi di Torino, c.so Svizzera 185, 10149 Torino, Italy; beatrice@di.unito.it.

a3 Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy; pighizzi@dsi.unimi.it.

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 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.

(Received December 13 2001)

(Accepted March 15 2002)

(Online publication August 15 2002)

Key Words:

  • Deterministic;
  • nondeterministic;
  • probabilistic;
  • quantum unary finite automata.

Mathematics Subject Classification:

  • 68Q10;
  • 68Q19;
  • 68Q45