Paper “On fixed points of the lower set operator” published in Internat. J. Algebra Comput.

The following paper has been published:

El siguiente artículo ha sido publicado:

El següent article ha sigut publicat:

J. Almeida, A. Cano, O. Klíma, J.-É. Pin

On fixed points of the lower set operator

Internat. J. Algebra Comput., 25(1-2) (2015), 259–292

http://dx.doi.org/10.1142/S021819671540010X

Abstract

Lower subsets of an ordered semigroup form in a natural way an ordered semigroup. This lower set operator gives an analogue of the power operator already studied in semigroup theory. We present a complete description of the lower set operator applied to varieties of ordered semigroups. We also obtain large families of fixed points for this operator applied to pseudovarieties of ordered semigroups, including all examples found in the literature. This is achieved by constructing six types of inequalities that are preserved by the lower set operator. These types of inequalities are shown to be independent in a certain sense. Several applications are also presented, including the preservation of the period for a pseudovariety of ordered semigroups whose image under the lower set operator is proper.Read More: http://www.worldscientific.com/doi/10.1142/S021819671540010X

2010 Mathematics subject classificationPrimary: 20M07, Secondary: 20M35

Keywords: Ordered semigroups; pseudovarieties; lower sets; power operator; inequalities; pseudoidentities

Paper “Regular languages and partial commutations” published in Inform. and Comput.

The following paper has been published.

El siguiente artículo ha sido publicado.

El següent article ha sigut publicat.

Antonio Cano, Giovanna Guaiana, Jean-Éric Pin

Regular languages and partial commutations

Inform. and Comput., 230, 79-96 (2013)

http://dx.doi.org/10.1016/j.ic.2013.07.003

Abstract

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 sufficient 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 defined as the largest positive variety of languages not containing (ab )∗. It is also closed under intersection, union, shuffle, 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, finiteness conditions on semigroups and properties of insertion systems.

Keywords: regular language, partial commutation, trace language, shuffle, variety of languages