Displaying similar documents to “On structural unambiguity of formal 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...