Transitive Closures of Semi-commutation Relations on Regular omega-Languages - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2007

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

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.
Fichier principal
Vignette du fichier
Heam.pdf (193.14 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00158285 , version 1 (28-06-2007)
inria-00158285 , version 2 (04-07-2007)

Identifiers

  • HAL Id : inria-00158285 , version 1

Cite

Pierre-Cyrille Heam. Transitive Closures of Semi-commutation Relations on Regular omega-Languages. [Research Report] 2007, pp.20. ⟨inria-00158285v1⟩
117 View
143 Download

Share

Gmail Facebook X LinkedIn More