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

A Compositional Approach to Synchronize Two Dimensional Networks of Processors

Salvatore La Torre, Margherita Napoli, Mimmo Parente (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of rows and columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of ( × ) processors and give some general constructions to synchronize arrays of ( × ) processors. Algorithms are given to synchronize in time , n ⌈ log n ⌉ , n ⌈ n ⌉ and 2 a square array of ( × ) processors. Our...