Paper «Languages associated with saturated formations of groups» published in Forum Math.

The following paper has been published:

El siguiente artículo ha sido publicado:

El següent article ha sigut publicat:

Adolfo Ballester-Bolinches, Jean-Éric Pin, Xaro Soler-Escrivà

Languages associated with saturated formations of groups

Forum Math., 27(3) (2015), 1471–1505

http://dx.doi.org/10.1515/forum-2012-0161

Abstract

In a previous paper, the authors have shown that Eilenberg’s variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower.

2010 Mathematics subject classification68Q70; 20D10

KeywordsGroup formation; regular language; finite automata; finite monoid

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

Paper «Languages associated with saturated formations of groups» to appear in Forum Math.

The paper

Adolfo Ballester-Bolinches, Jean-Éric Pin, Xaro Soler-Escrivà

Languages associated with saturated formations of groups

will be published in Forum Mathematicum. It is available through

http://dx.doi.org/10.1515/forum-2012-0161

We will inform about the publication details. See abstract below.

El artículo

Adolfo Ballester-Bolinches, Jean-Éric Pin, Xaro Soler-Escrivà

Languages associated with saturated formations of groups

será publicado en Forum Mathematicum. Está disponible en

http://dx.doi.org/10.1515/forum-2012-0161

Informaremos sobre los detalles de publicación. Véase el resumen más abajo.

 

L’article

Adolfo Ballester-Bolinches, Jean-Éric Pin, Xaro Soler-Escrivà

Languages associated with saturated formations of groups

serà publicat en Forum Mathematicum. Està disponible a

http://dx.doi.org/10.1515/forum-2012-0161

Informarem sobre els detalls de publicació. Vegeu el resum més avall.

 

Abstract

In a previous paper, the authors have shown that Eilenberg’s variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower.

Keywords: Group formation; regular language;finite automata; finite monoid