Displaying similar documents to “Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata”

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

A characterization of poly-slender context-free languages

Lucian Ilie, Grzegorz Rozenberg, Arto Salomaa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

For a non-negative integer , we say that a language is if the number of words of length in is of order 𝒪 ( n k ) . We give a precise characterization of the -poly-slender context-free languages. The well-known characterization of the -poly-slender regular languages is an immediate consequence of ours.

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

Carlo Mereghetti, Beatrice Palano (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that, for any stochastic event of period , there exists a with at most 2 6 n + 25 states inducing the event , for constants , ≥ 0, satisfying + ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period can be accepted with isolated cut point by a 1qfa with no more than 2 6 n + 26 states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical...