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.