Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {} of cyclic languages, where = | ∈ . In particular, we show that, for any , the number of states necessary and sufficient for accepting the unary language with isolated cut point on one-way probabilistic finite automata is , with being the factorization of . To prove this result, we give a Moreover, we exhibit one-way quantum...