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 4 Next

Displaying 61 – 80 of 107

Showing per page

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

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

Normal Subgroup of Product of Groups

Hiroyuki Okazaki, Kenichi Arai, Yasunari Shidama (2011)

Formalized Mathematics

In [6] it was formalized that the direct product of a family of groups gives a new group. In this article, we formalize that for all j ∈ I, the group G = Πi∈IGi has a normal subgroup isomorphic to Gj. Moreover, we show some relations between a family of groups and its direct product.

Normalization of edit sequences for text synchronization

Rafael C. Carrasco, Alexander Sánchez Díaz (2011)

RAIRO - Theoretical Informatics and Applications

It often occurs that local copies of a text are modified by users but that the local modifications are not synchronized (thus allowing the merged text to become the source for later editions) until later when, for instance the network connection is reestablished. Since text editions usually affect a small fraction of the whole content, the history of edit operations provides a compact representation of the modified file. In this paper, we define a normal form for these records which will...

Normalization of edit sequences for text synchronization

Rafael C. Carrasco, Alexander Sánchez Díaz (2011)

RAIRO - Theoretical Informatics and Applications

It often occurs that local copies of a text are modified by users but that the local modifications are not synchronized (thus allowing the merged text to become the source for later editions) until later when, for instance the network connection is reestablished. Since text editions usually affect a small fraction of the whole content, the history of edit operations provides a compact representation of the modified file. In this paper, we define a normal form for these records which will...

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

Note on universal algorithms for learning theory

Karol Dziedziul, Barbara Wolnik (2007)

Applicationes Mathematicae

We study the universal estimator for the regression problem in learning theory considered by Binev et al. This new approach allows us to improve their results.

Currently displaying 61 – 80 of 107