A Topological Approach to Recognition

Résumé : Nous proposons une nouvelle approche de la notion de reconnaissance, qui diffère des définitions classiques par trois aspects particuliers. Tout d'abord, notre approche n'utilise pas du tout les automates. Ensuite, elle s'applique à des algèbres de Boole de parties plutôt qu'à des ensembles pris individuellement. Enfin elle repose sur la topologie. Nous montrons l'existence d'un reconnaisseur minimal dans un cadre très général qui s'applique en particulier à n'importe quelle algèbre de Boole de parties d'un espace discret. Nos résultats principaux montrent que ce reconnaisseur minimal est un espace uniforme dont la complétion est le dual de l'algèbre de Boole considérée pour la dualité de Stone-Priestley. Dans le cas d'une algèbre de Boole de langages fermée par quotient, cette complétion, appelée l'espace syntactique de l'algèbre de Boole, est un monoïde compact si et seulement si tous les langages de l'algèbre de Boole sont reconnaissables. Dans le cas des langages reconnaissables, on retrouve ainsi les notions de monoïde syntactique et de monoïde profini libre. Pour les langages non reconnaissables, l'espace syntactique est toujours un espace compact mais n'est plus un monoïde. Par ailleurs, nous donnons une description équationnelle des algèbres de Boole fermées par quotient, qui étend aux langages non reconnaissables les résultats connus sur les langages reconnaissables. Finalement, nous généralisons tous ces résultats des algèbres de Boole aux treillis, cas dans lequel les structures topologiques sont partiellement ordonnées.
Type de document :
Communication dans un congrès
Abramsky, S. et al. ICALP 2010, Jul 2010, Bordeaux, France. Springer, Proceedings ICALP 2010, Part II,, 6199, pp.151 - 162, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-14162-1_13〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-01101846
Contributeur : Jean-Eric Pin <>
Soumis le : vendredi 9 janvier 2015 - 18:57:34
Dernière modification le : vendredi 4 janvier 2019 - 17:32:57
Document(s) archivé(s) le : vendredi 11 septembre 2015 - 06:28:02

Fichier

ICALP2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mai Gehrke, Serge Grigorieff, Jean-Eric Pin. A Topological Approach to Recognition. Abramsky, S. et al. ICALP 2010, Jul 2010, Bordeaux, France. Springer, Proceedings ICALP 2010, Part II,, 6199, pp.151 - 162, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-14162-1_13〉. 〈hal-01101846〉

Partager

Métriques

Consultations de la notice

220

Téléchargements de fichiers

201