Duality and equational theory of regular languages

• Main Authors: Gehrke, Mai, Grigorieff, Serge, Pin, Jean-Eric
• Other Authors: Institute for Mathematics, Astrophysics and Particle Physics (IMAPP), Radboud University Nijmegen, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2008
• Subjects: Stone duality; regular language; equational theory; profinite topology; [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]; [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; [MATH.MATH-GN]Mathematics [math]/General Topology [math.GN]; Iceland
• Online Access: https://hal.science/hal-00340803; https://hal.science/hal-00340803/document; https://hal.science/hal-00340803/file/DualityWeb.pdf

Best paper award of ICALP 2008, Track B International audience 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 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.