Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Regular languages and partial commutations

  • Cano Gómez, Antonio
  • Guaiana, Giovanna
  • Pin, Jean-Eric
[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., The first author was supported by the project Automatas en dispositivos moviles: interfaces de usuario y realidad aumentada (PAID 2019-06-11) supported by Universidad Politecnica de Valencia. The third author was supported by the project ANR 2010 BLAN 0202 02 FREC.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Upper set monoids and length preserving morphisms

  • Cano Gómez, Antonio
  • Pin, Jean-Eric
Length preserving morphisms and inverse of substitutions are two well-studied operations on regular languages. Their connection with varieties generated by power monoids was established independently by Reutenauer and Straubing in 1979. More recently, an ordered version of this theory was proposed by Polák and by the authors. In this paper, we present an improved version of these results and obtain the following consequences. Given a variety of finite ordered monoids V, let P ¿V be the variety of finite ordered monoids generated by the upper set monoids of members of V. Then P ¿(P ¿V)=P ¿V. This contrasts with the known results for the unordered case: the operator PV corresponding to power monoids satisfies P 3V=P 4V, but the varieties V, PV, P 2V and P 3V can be distinct. © 2011 Elsevier B.V., Work supported by the integrated action Picasso 19245ZC and by the AuthoMathA Programme of the European Science Foundation. The first author was supported by the project Tecnicas de Inferencia Gramatical y aplicacion al procesamiento de biosecuencias (TIN2007-60769) supported by the Spanish Ministry of Education and Sciences. The second author was supported by the project ANR 2010 BLAN 0202 02 FREC.