Mixed languages

• Published in: Theoretical computer science 2005-02, Vol.332 (1), p.179-198
• Main Authors: Berstel, Jean, Boasson, Luc, Latteux, Michel
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer Science; Computer science; control theory; systems; Discrete Mathematics; Exact sciences and technology; Formal languages; Language theory and syntactical analysis; Synchronized product; Theoretical computing; Theory of traces
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2004.08.016

Let T = A ∪ B ∪ C be an alphabet that is partitioned into three subalphabets. The mixing product of a word g over A ∪ B and of a word d over A ∪ C is the set of words w over T such that its projection onto A ∪ B gives g and its projection onto A ∪ C gives d. Let R be a regular language over T such that xbcy is in R if and only if xcby is in R for any two letters b in B and c in C. In other words, R is commutative over B and C. Is this property “structural” in the sense that R can then be obtained as a mixing product of a regular language over A ∪ B and of a regular language over A ∪ C ? This question has a rather easy answer, but there are many cases where the answer is negative. A more interesting question is whether R can be represented as a finite union of mixed products of regular languages. For the moment, we do not have an answer to this question. However, we prove that it is decidable whether, for a given k, the language R is a union of at most k mixed products of regular languages. Soit T = A ∪ B ∪ C un alphabet partitionné en trois sous-alphabets. Le mélange d’un mot g sur A ∪ B et d’un mot d sur A ∪ C est l’ensemble des mots w sur T dont la projection sur A ∪ B donne le mot g et sur A ∪ C donne le mot d. Soit R un langage rationnel sur T tel que xbcy est dans R si et seulement si xcby est dans R pour deux lettres quelconques b ∈ B et c ∈ C . En d’autres termes, R est commutatif sur B et C. Est-ce que cette propriété est “structurelle”, c’est-à-dire peut-on alors obtenir R comme mélange d’un langage rationnel sur A ∪ B et d’un langage rationnel sur A ∪ C ? Cette question a une réponse plutôt facile, mais il existe de trop nombreux cas où la réponse est négative. Une question plus intéressante est de savoir si on peut représenter R comme une union finie de mélanges de langages rationnels. Pour l’instant, nous n’avons pas de réponse à cette question. En revanche, nous montrons qu’il est décidable, pour un entier k donné, si R est union d’au plus k mélanges de langages rationnels.