Normal forms for unary probabilistic automata

Maria Paola Bianchi; Giovanni Pighizzini

Displaying similar documents to “Normal forms for unary probabilistic automata”

Normal forms for unary probabilistic automata

Maria Paola Bianchi, Giovanni Pighizzini (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension...

Normal forms for unary probabilistic automata

Maria Paola Bianchi, Giovanni Pighizzini (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family ${L_{m}}$ of cyclic languages, where $L_{m} = {a^{k m} | k \in ℕ}$ . In particular, we show that, for any $m$ , the number of states necessary and sufficient for accepting the unary language $L_{m}$ 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 $m$ . To prove this result, we give a general state lower bound for accepting unary languages with isolated...

On one language with connection to determinism and bounded deleting

Martin Procházka (2000)

Acta Mathematica et Informatica Universitatis Ostraviensis

Similarity:

Returning and non-returning parallel communicating finite automata are equivalent

Ashish Choudhary, Kamala Krithivasan, Victor Mitrana (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.

Systems of parallel communicating restarting automata

Marcel Vollweiler, Friedrich Otto (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols,...

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained...