All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 23 Next

Displaying 441 – 460 of 948

Showing per page

Normal forms for unary probabilistic automata

Maria Paola Bianchi, Giovanni Pighizzini (2012)

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

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 to the probabilistic case of Chrobak normal form, obtained...

Normal forms for unary probabilistic automata

Maria Paola Bianchi, Giovanni Pighizzini (2012)

RAIRO - Theoretical Informatics and Applications

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

Note on the complexity of Las Vegas automata problems

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger [Theoret....

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

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 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 + ⋯ + p s α s , with p 1 α 1 p 2 α 2 ⋯ 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 cut point on...

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

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2010)

RAIRO - Theoretical Informatics and Applications

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

On a class of infinitary codes

Nguyen Huong Lâm, Do Long Van (1990)

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

On a complete set of operations for factorizing codes

Clelia De Felice (2006)

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

It is known that the class of factorizing codes, i.e., codes satisfying the factorization conjecture formulated by Schützenberger, is closed under two operations: the classical composition of codes and substitution of codes. A natural question which arises is whether a finite set 𝒪 of operations exists such that each factorizing code can be obtained by using the operations in 𝒪 and starting with prefix or suffix codes. 𝒪 is named here a complete set of operations (for factorizing codes). We show...

On a complete set of operations for factorizing codes

Clelia De Felice (2010)

RAIRO - Theoretical Informatics and Applications

It is known that the class of factorizing codes, i.e., codes satisfying the factorization conjecture formulated by Schützenberger, is closed under two operations: the classical composition of codes and substitution of codes. A natural question which arises is whether a finite set O of operations exists such that each factorizing code can be obtained by using the operations in O and starting with prefix or suffix codes. O is named here a complete set of operations (for factorizing codes). We show...

On a test for codes.

Falucskai, J. (2006)

Acta Mathematica Academiae Paedagogicae Nyí regyháziensis. New Series [electronic only]

On ambiguity in DOS systems

Andrzej Ehrenfeucht, David Haussler, Grzegorz Rozenberg (1984)

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

Currently displaying 441 – 460 of 948