Displaying similar documents to “Linear size test sets for certain commutative languages”

Parikh test sets for commutative languages

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

Equality sets for recursively enumerable languages

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 E G ( a , g 1 , g 2 ) = { w g 1 ( w ) = a g 2 ( w ) } , where g 1 and g 2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h ( E G ( J ) ) , where h is a coding and E G ( J ) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L A * is a projection of a shifted equality set, that is, L = π A ( E G ( a , g 1 , g 2 ) ) for some (nonerasing) morphisms g 1 and g 2 and a letter a , where π A deletes the letters not in A . Then...

On conjugacy of languages

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 X and Y are conjugates if they satisfy the conjugacy equation X Z = Z Y for some language Z . We study several problems associated with this equation. For example, we characterize all sets which are conjugated v i a a two-element biprefix set Z , as well as all two-element sets which are conjugates.

A test-set for k -power-free binary morphisms

F. Wlazinski (2001)

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

Similarity:

A morphism f is k -power-free if and only if f ( w ) is k -power-free whenever w is a k -power-free word. A morphism f is k -power-free up to m if and only if f ( w ) is k -power-free whenever w is a k -power-free word of length at most m . Given an integer k 2 , we prove that a binary morphism is k -power-free if and only if it is k -power-free up to k 2 . This bound becomes linear for primitive morphisms: a binary primitive morphism is k -power-free if and only if it is k -power-free up to 2 k + 1 ...

Efficiency of automata in semi-commutation verification techniques

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 L – called APC – of the form j L 0 , j L 1 , j L 2 , j ... L k j , j , where the union is finite and each L i , j is either a single symbol or a language of the form B * with B a subset of the alphabet, is...

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2002)

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

Similarity:

For any finite word w on a finite alphabet, we consider the basic parameters R w and K w of w defined as follows: R w is the minimal natural number for which w has no right special factor of length R w and K w is the minimal natural number for which w has no repeated suffix of length K w . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.