Duality and equational theory of regular languages

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 cl...

Full description

Bibliographic Details
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]
Priestley
Iceland
Online Access:https://hal.science/hal-00340803
https://hal.science/hal-00340803/document
https://hal.science/hal-00340803/file/DualityWeb.pdf
Description
Summary: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.

Similar Items