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...
Main Authors: | , , |
---|---|
Other Authors: | , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2008
|
Subjects: | |
Online Access: | https://hal.science/hal-00340803 https://hal.science/hal-00340803/document https://hal.science/hal-00340803/file/DualityWeb.pdf |
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. |
---|