Paper «A positive extension of Eilenberg’s variety theorem for non-regular languages» published in Appl. Algebra Eng. Commun. Comp.

The following paper has been published:
El siguiente artículo ha sido publicado:
El següent article ha sigut publicat:

A. Cano, J. Cantero, A. Martínez-Pastor.
A positive extension of Eilenberg’s variety theorem for non-regular languages.
Appl. Algebra Eng. Commun. Comp., 32:553-573, 2021.

doi: 10.1007/s00200-020-00414-2

Abstract:

In this paper we go further with the study initiated by Behle, Krebs and Reifferscheid (in: Proceedings CAI 2011, Lecture Notes in Computer Science, vol 6742, pp 97–114, 2011), who gave an Eilenberg-type theorem for non-regular languages via typed monoids. We provide a new extension of that result, inspired by the one carried out by Pin in the regular case in 1995, who considered classes of languages not necessarily closed under complement. We introduce the so-called positively typed monoids, and give a correspondence between varieties of such algebraic structures and positive varieties of possibly non-regular languages. We also prove a similar result for classes of languages with weaker closure properties.

2020 Mathematics Subject Classification: 68Q70, 68Q45, 20M07, 20M35.

Keywords: monoids, varieties, formal languages.

Visita i xarrada professor Jean-Éric Pin 24/02/2020

Feb ’20
24
12:00

Jean-Éric PinBenvolgudes companyes, benvolguts companys,

El professor Jean-Éric Pin (IRIF, CNRS i Université Paris-Diderot) ens visitarà el proper dilluns 24 de febrer i impartirà la xarrada

«Formations of monoids»

el proper dilluns 24 de febrer a les 12.00 a l’aula 1.5 de la Facultat de Matemàtiques.

Ben cordialment,

Ramon

Paper «Some contributions to the theory of transformation monoids» published in J. Algebra

The following paper has been published:

El siguiente artículo ha sido publicado:

El següent article ha sigut publicat:

A. Ballester-Bolinches, E. Cosme-Llópez, P. Jiménez-Seral.

Some contributions to the theory of transformation monoids

J. Algebra., 522:31-60, 2019

doi:10.1016/j.jalgebra.2018.12.005

Abstract

The aim of this paper is to present some contributions to the theory of finite transformation monoids. The dominating influence that permutation groups have on transformation monoids is used to describe and characterise transitive transformation monoids and primitive transitive transformation monoids. We develop a theory that not only includes the analogs of several important theorems of the classical theory of permutation groups but also contains substantial information about the algebraic structure of the transformation monoids. Open questions naturally arising from the substantial paper of Steinberg (2010) [11] have been answered. Our results can also be considered as a further development in the hunt for a solution of the Černý conjecture.

2010 Mathematics Subject Classification: 16W22, 20M30

Keywords: monoid theory, monoid action, transitive, faithful, primitive

Paper «A noncommutative extension of Mahler’s theorem on interpolation series» published in European J. Combin.

The following paper has been published.

El siguiente artículo ha sido publicado.

El següent article ha sigut publicat.

Jean-Éric Pin, Pedro V. Silva

A noncommutative extension of Mahler’s theorem on interpolation series

European J. Combin., 36, 564-578 (2014)

http://dx.doi.org/10.1016/j.ejc.2013.09.009

Abstract

In this paper, we prove an extension of Mahler’s theorem on interpolation series, a celebrated result of p-adic analysis. Mahler’s original result states that a function from N to Z is uniformly continuous for the p-adic metric dp if and only if it can be uniformly approximated by polynomial functions. We prove the same result for functions from a free monoid A∗ to Z, where dp is replaced by the pro-p metric, the profinite metric on A∗ defined by p-groups.