Regular languages and partial commutations

Autores UPV
Año
Revista INFORMATION AND COMPUTATION

Abstract

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.