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.archives-ouvertes.fr/hal-00340803 https://hal.archives-ouvertes.fr/hal-00340803/document https://hal.archives-ouvertes.fr/hal-00340803/file/DualityWeb.pdf |
id |
ftccsdartic:oai:HAL:hal-00340803v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-00340803v1 2023-05-15T16:50:44+02:00 Duality and equational theory of regular languages Gehrke, Mai Grigorieff, Serge Pin, Jean-Eric 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) Reykjavik, Iceland 2008-07 https://hal.archives-ouvertes.fr/hal-00340803 https://hal.archives-ouvertes.fr/hal-00340803/document https://hal.archives-ouvertes.fr/hal-00340803/file/DualityWeb.pdf en eng HAL CCSD hal-00340803 https://hal.archives-ouvertes.fr/hal-00340803 https://hal.archives-ouvertes.fr/hal-00340803/document https://hal.archives-ouvertes.fr/hal-00340803/file/DualityWeb.pdf info:eu-repo/semantics/OpenAccess Proceedings of ICALP 2008, Part II ICALP 2008 https://hal.archives-ouvertes.fr/hal-00340803 ICALP 2008, Jul 2008, Reykjavik, Iceland. pp.246-257 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] info:eu-repo/semantics/conferenceObject Conference papers 2008 ftccsdartic 2021-12-05T03:54:15Z 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. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) Priestley ENVELOPE(161.883,161.883,-75.183,-75.183) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
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] |
spellingShingle |
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] Gehrke, Mai Grigorieff, Serge Pin, Jean-Eric Duality and equational theory of regular languages |
topic_facet |
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] |
description |
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. |
author2 |
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 |
author |
Gehrke, Mai Grigorieff, Serge Pin, Jean-Eric |
author_facet |
Gehrke, Mai Grigorieff, Serge Pin, Jean-Eric |
author_sort |
Gehrke, Mai |
title |
Duality and equational theory of regular languages |
title_short |
Duality and equational theory of regular languages |
title_full |
Duality and equational theory of regular languages |
title_fullStr |
Duality and equational theory of regular languages |
title_full_unstemmed |
Duality and equational theory of regular languages |
title_sort |
duality and equational theory of regular languages |
publisher |
HAL CCSD |
publishDate |
2008 |
url |
https://hal.archives-ouvertes.fr/hal-00340803 https://hal.archives-ouvertes.fr/hal-00340803/document https://hal.archives-ouvertes.fr/hal-00340803/file/DualityWeb.pdf |
op_coverage |
Reykjavik, Iceland |
long_lat |
ENVELOPE(161.883,161.883,-75.183,-75.183) |
geographic |
Priestley |
geographic_facet |
Priestley |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Proceedings of ICALP 2008, Part II ICALP 2008 https://hal.archives-ouvertes.fr/hal-00340803 ICALP 2008, Jul 2008, Reykjavik, Iceland. pp.246-257 |
op_relation |
hal-00340803 https://hal.archives-ouvertes.fr/hal-00340803 https://hal.archives-ouvertes.fr/hal-00340803/document https://hal.archives-ouvertes.fr/hal-00340803/file/DualityWeb.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766040856619384832 |