Polynomial size test sets for commutative languages
Ismo Hakala, Juha Kortelainen (1997)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Ismo Hakala, Juha Kortelainen (1997)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Štěpán Holub (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
A set is a Parikh test set of if is a test set of . We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.
Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2005)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter , where deletes the letters not in . Then...
Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We say that two languages and are conjugates if they satisfy the conjugacy equation for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
F. Wlazinski (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
A morphism is -power-free if and only if is -power-free whenever is a -power-free word. A morphism is -power-free up to if and only if is -power-free whenever is a -power-free word of length at most . Given an integer , we prove that a binary morphism is -power-free if and only if it is -power-free up to . This bound becomes linear for primitive morphisms: a binary primitive morphism is -power-free if and only if it is -power-free up to ...
L. Rosaz (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Gérard Cécé, Pierre-Cyrille Héam, Yann Mainier (2008)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Computing the image of a regular language by the transitive closure of a relation is a central question in regular model checking. In a recent paper Bouajjani et al. [IEEE Comput. Soc. (2001) 399–408] proved that the class of regular languages – called APC – of the form , where the union is finite and each is either a single symbol or a language of the form with a subset of the alphabet, is...
Arturo Carpi, Aldo de Luca (2002)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.