Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic 
and Quantum Finite Automata

Carlo Mereghetti; Beatrice Palano; Giovanni Pighizzini

Skip to main content (access key 's'), Skip to navigation (access key 'n'), Accessibility information (access key '0')

The search session has expired. Please query the service again.

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 ⌈ \sqrt{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.