Regular languages and partial commutations

Abstract

[EN] The closure of a regular language under a [partial] commutation I has been extensively studied. We present new advances on two problems of this area: (1) When is the closure of a regular language under [partial] commutation still regular? (2) Are there any robust classes of languages closed under [partial] commutation? We show that the class Pol(G) of polynomials of group languages is closed under commutation, and under partial commutation when the complement of I in A2 is a transitive relation. We also give a su¿cient graph theoretic condition on I to ensure that the closure of a language of Pol(G) under I-commutation is regular. We exhibit a very robust class of languages W which is closed under commutation. This class contains Pol(G), is decidable and can be de¿ned as the largest positive variety of languages not containing (ab)¿. It is also closed under intersection, union, shu¿e, concatenation, quotients, length-decreasing morphisms and inverses of morphisms. If I is transitive, we show that the closure of a language of W under I-commutation is regular. The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid, ¿niteness conditions on semigroups and properties of insertion systems. © 2013 Elsevier Inc. All rights reserved

[ES] El cierre de un lenguaje regular bajo una conmutación [parcial] $I$ se ha estudiado extensivamente. Presentamos nuevos avances sobre los dos problemas de esta zona: (1) cuando es el cierre de un lenguaje regular bajo ¿conmutación [parcial] todavía regular? (2) Hay alguna clase robusta ¿de idiomas cerraron bajo conmutación [parcial]? Demostramos que la clase $\PolG$ de polinomios de grupo idiomas está cerrada bajo conmutación y bajo conmutación parcial cuando el complemento de $ $I en $A ^ 2$ es una relación transitiva. También damos un gráfico suficiente condición teórica en $ $I para asegurarse de que el cierre de un lenguaje de \PolG$ $ bajo $lo$-conmutación es regular. Exhibimos un muy robusto clase de idiomas $\cW$ que es cerrado bajo conmutación. Esta clase contiene \PolG$ $, es decidible y puede definirse como el más grande positiva variedad de idiomas que no contengan $(ab) ^ * $. También es cerrado bajo intersección, Unión, shuffle, concatenación, cocientes, longitud decreciente morfismos e inversas de morfismos. Si $ $I es transitivo, demostramos que el cierre de un lenguaje de $\cW$ bajo $Lo$-conmutación es regular. Las pruebas son no triviales y se combinan varias técnicas avanzadas, incluyendo el tipo de Ramsey combinatoria argumentos, propiedades algebraicas de la monoid sintáctica, finito condiciones sobre semigrupos y propiedades de los sistemas de inserción.