Author manuscript, published in "ICALP 2008, Reykjavik: Islande (2008)" Duality and equational theory of regular languages

• Main Authors: Mai Gehrke, Serge Grigorieff, Jean-éric Pin
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 2008
• Subjects: Priestley; McNaughton; Islande
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.382.9883; http://hal.archives-ouvertes.fr/docs/00/34/08/03/PDF/DualityWeb.pdf

This paper presents a new result in the equational theory of regular languages, which emerged from lively discussions between the authors about Stone and Priestley duality. Let us call lattice of languages a class of regular languages closed under finite intersection and finite union. The main results of this paper (Theorems 5.2 and 6.1) can be summarized in a nutshell as follows: A set of regular languages is a lattice of languages if and only if it can be defined by a set of profinite equations. The product on profinite words is the dual of the residuation operations on regular languages. In their more general form, our equations are of the form u → v, where u and v are profinite words. The first result not only subsumes Eilenberg-Reiterman’s theory of varieties and their subsequent extensions, but it shows for instance that any class of regular languages defined by a fragment of logic closed under conjunctions and disjunctions (first order, monadic second order, temporal, etc.) admits an equational description. In particular, the celebrated McNaughton-