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


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.

Paper «Varieties and covarieties of languages (extended abstract)» published in Electron. Notes Theor. Comput. Sci.

The following paper has been published.

El siguiente artículo ha sido publicado.

El següent article ha sigut publicat.

Jan Rutten, Adolfo Ballester-Bolinches, Enric Cosme-Llópez

Varieties and covarieties of languages (extended abstract)

Electron. Notes Theor. Comput. Sci., 298, 7-28 (2013)

Abstract: Because of the isomorphism (X × A) → X =∼ X → (A → X), the transition structure of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. This algebra-coalgebra duality goes back to Arbib and Manes, who formulated it as a duality between reachability and observability, and is ultimately based on Kalman’s duality in systems theory between controllability and observability. Recently, it was used to give a new proof of Brzozowski’s minimization algorithm for deterministic automata. Here we will use the algebra-coalgebra duality of automata as a common perspective for the study of both varieties and covarieties, which are classes of automata and languages defined by equations and coequations, respectively. We make a first connection with Eilenberg’s definition of varieties of languages, which is based on the classical, algebraic notion of varieties of (transition) monoids.
Automata, variety, covariety, equation, coequation, algebra, coalgebra.