Author manuscript, published in "ICALP 2008, Reykjavik: Islande (2008)" Duality and equational theory of regular languages
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 resul...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Text |
| Language: | English |
| Published: |
2008
|
| Subjects: | |
| 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 |
| Summary: | 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- |
|---|