Displaying similar documents to “A hierarchy of cyclic languages”

Circular splicing and regularity

Paola Bonizzoni, Clelia De Felice, Giancarlo Mauri, Rosalba Zizza (2004)

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

Similarity:

Circular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages X * , called here star languages,...

State complexity of cyclic shift

Galina Jirásková, Alexander Okhotin (2008)

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

Similarity:

The cyclic shift of a language L , defined as s h i f t ( L ) = { v u | u v ∈ L } , is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! · 2 ( n - 1 ) ( n - 2 ) , which shows that the...

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

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