Displaying similar documents to “A characterization of poly-slender context-free languages”

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 p 1 α 1 + p 2 α 2 + ⋯ + p s α s , with p 1 α 1 p 2 α 2 ⋯ p s α s being the factorization of . To prove this result, we give a Moreover, we exhibit one-way quantum...

A Lower Bound For Reversible Automata

Pierre-Cyrille Héam (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A reversible automaton is a finite automaton in which each letter induces a partial one-to-one map from the set of states into itself. We solve the following problem proposed by Pin. Given an alphabet , does there exist a sequence of languages on which can be accepted by a reversible automaton, and such that the number of states of the minimal automaton of is in (), while the minimal number of states of a reversible automaton accepting ...