Transitive Closures of Semi-commutation Relations on Regular omega-Languages

Pierre-Cyrille Héam 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A semi-commutation $R$ is a relation on a finite alphabet $A$. Given an infinite word $u$ on $A$, we denote by $R(u)=\{xbay\mid x\in A^*,y\in A^\omega \ (a,b)\in R \text{ and } xaby=u\}$ and by $R^*(u)$ the language $\{u\}\cup \cup_{k\geq 1} R^k(u)$. In this paper we prove that if an $\omega$-language $L$ is a finite union of languages of the form $A_0^*a_1A_1^*\ldots a_k A_k^*a_{k+1}A_{k+1}^*$, where the $A_i$'s are subsets of the alphabet and the $a_i$'s are letters, then $R^*(L)$ is a computable regular $\omega$-language accepting a similar decomposition. In addition we prove the same result holds for $\omega$-languages which are finite unions of languages of the form $L_0a_1L_1\ldots a_k L_ka_{k+1}L_{k+1}$, where the $L_i$'s are accepted by diamond automata and the $a_i$'s are letters. These results improve recent works by Bouajjani, Muscholl and Touili on one hand, and by Cécé, Héam and Mainier on the other hand, by extending them to infinite words.
Type de document :
Rapport
[Research Report] RR-6239, INRIA. 2007, pp.20
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00158285
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 4 juillet 2007 - 14:28:25
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:17:21

Fichiers

RR-6239.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00158285, version 2

Citation

Pierre-Cyrille Héam. Transitive Closures of Semi-commutation Relations on Regular omega-Languages. [Research Report] RR-6239, INRIA. 2007, pp.20. 〈inria-00158285v2〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

104