On the Size of One-way Quantum Finite Automata with Periodic Behaviors

Carlo Mereghetti; Beatrice Palano

Displaying similar documents to “On the Size of One-way Quantum Finite Automata with Periodic Behaviors”

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}} + \dots + p_{s}^{α_{s}}$ , with $p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{s}^{α_{s}}$ being the factorization of . To prove this result, we give a Moreover, we exhibit one-way quantum...

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 ⌈ \sqrt{n} ⌉$ and 2 a square array of ( × ) processors. Our...

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We present an algorithm for computing the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have -transitions. The prefix automaton of an automaton $𝒜$ has the following characteristic properties. It has the same graph as $𝒜$ . Each accepting path has the same label as in $𝒜$ . For each state , the longest common prefix of the labels of all paths going from to an initial or final state is empty. The interest of the computation of the prefix...

Towards parametrizing word equations

H. Abdulrab, P. Goralčík, G. S. Makanin (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Classically, in order to resolve an equation ≈ over a free monoid *, we reduce it by a suitable family $ℱ$ of substitutions to a family of equations ≈ , $f \in ℱ$ , each involving less variables than ≈ , and then combine solutions of ≈ into solutions of ≈ . The problem is to get $ℱ$ in a handy form. The method we propose consists in parametrizing the path traces in the so called associated to ≈ . We carry out such a parametrization in the case the prime equations in the graph involve at...