Langues régulières du point de vue théorique de la catégorie

21

J'ai remarqué que les langues régulières sur l'alphabet peuvent naturellement être considérées comme un poset, et même un treillis. De plus, la concaténation avec le langage vide définit une structure monoïdale stricte sur cette catégorie qui est distributive sur les jointures (je ne suis pas sûr des rencontres). Est-ce une construction utile en théorie ou en pratique des langues régulières? Y a-t-il de belles adjonctions à trouver, par exemple pouvons-nous définir l'étoile de Kleene comme une?Σϵ

Ceci est une copie d'une question posée lors du cours Compilers à Coursera: https://class.coursera.org/compilers/forum/thread?thread_id=311

Alexei Averchenko
la source
4
Il suffit de souligner que le lien nécessite que l'on puisse se connecter au site Web de coursea.
Dave Clarke
1
Quel est l'ordre partiel qui fait des langues régulières un poset? est-ce simplement la propriété du sous-ensemble?
Suresh Venkat
@Suresh Oui, ai-je raté quelque chose?
Alexei Averchenko
1
Non. Je voulais juste comprendre s'il y avait quelque chose de plus spécifique à la structure du langage
Suresh Venkat
@Suresh Je ne suis certainement pas aussi intelligent ou éduqué que les gens que Dave Clarke référence, donc je n'ai vu que la chose la plus évidente :)
Alexei Averchenko

Réponses:

18

Beaucoup a été fait pour appliquer la théorie des catégories aux langages et automates normaux. Un point de départ est les articles récents:

Dans le premier de ces articles, la structure des expressions régulières est traitée algébriquement et les langages générés sont traités par hégémonie. Ces deux vues sont intégrées dans un cadre bialgébrique. Un bialgebra est une paire algèbre-houille avec une loi distributive appropriée capturant l'interaction entre les termes syntaxiques (les expressions régulières) et le comportement de calcul (langages générés). La base de cet article est l'algèbre et la houille, traitées en informatique sous l'égide de l'algèbre universelle et de la houille, plutôt que ce que l'on voit en mathématiques (groupes, etc.).

Le deuxième article utilise des techniques issues du traitement mathématique plus traditionnel de l'algèbre (modules, etc.) et de la houille, mais je crains de ne pas en connaître les détails.

Pour autant que je sache, ni l'une ni l'autre ne considère l'étoile de Kleene comme une adjonction.

Plus généralement, il y a beaucoup de travail à appliquer la théorie des catégories aux automates au lieu des expressions régulières. Un échantillon de ce travail comprend:

Enfin, il y a le travail sur les théories d'itération, itération: la logique équationnelle des processus itératifs par Stephen L. Bloom et Zoltán Ésik, qui se concentre sur l'itération (par exemple, l'étoile de Kleene), mais d'un point de vue plus général, où les langues régulières ne sont que une chose qui relève de la théorie.

Dave Clarke
la source
2
Pour les automates, il y a aussi books.google.co.uk/…
Radu GRIGore
1
Malheureusement, le terme «algèbre» est galvaudé. Il y a le sens de "algèbre" en tant que structure algébrique générique, qui est utilisée dans l'algèbre universelle, les algèbres de foncteur et les algèbres de monade. Le papier de Bart Jacobs en parle. Il existe une structure plus spécifique appelée " algèbre " définie dans la théorie des anneaux / modules. L'article de James Worthington en traite. À mon avis, le travail de Worthington est beaucoup plus intéressant, mais je pense que nous avons seulement commencé à gratter la surface ici.
Uday Reddy
Lien non paywall vers l'article de Bart: repository.ubn.ru.nl/handle/2066/36207
Turion
12

En fait, je pense que ce que vous cherchez, c'est l'algèbre de Kleene. Voir l'article classique de Dexter Kozen. Il donne une axiomatisation de l'étoile de Kleene. Je suppose que c'est la toute première étape qui vous intéresse.

Un théorème de complétude pour les algèbres de Kleene et l'algèbre des événements réguliers. Information et calcul, 110 (2): 366-390, mai 1994.

Cet article n'utilise pas la théorie des catégories, mais il donne une axiomatisation équationnelle des algèbres de Kleene, dont la structure inclut celle des langages réguliers. Les algèbres de Kleene avec des tests peuvent être considérées comme l'extension des expressions régulières pour modéliser des programmes simples avec des boucles et des conditions (mais sans affectations). Cette extension est utile pour raisonner sur de tels programmes simples de manière purement algébrique.

Sur la théorie houillère de l'algèbre de Kleene avec des tests. Rapport technique. Université Cornell, mars 2008.

Les langues régulières forment une algèbre booléenne avec une structure supplémentaire, comme vous le constatez. Cette structure a été étudiée du point de vue de la dualité de la pierre par Nick Pippenger.

Langues régulières et dualité de pierre . Nicholas Pippenger. Theory Computing Systems, 1997: 121-134.

L'approche de la dualité de la reconnaissance de la langue a récemment été à l'honneur et a été appliquée pour obtenir de nouveaux résultats sur la reconnaissance de la langue.

Dualité et théorie équationnelle des langages réguliers. M. Gehrke, S. Grigorieff, J.-E. Épingle.

Vijay D
la source
1
Et spécifiquement sur certaines adjonctions classiques des algèbres de Kleene dans la théorie des machines: cs.cornell.edu/Courses/cs786/2004sp/Lectures/l06-adj.pdf
ex0du5
4

Regarder le monde à l'aide de lunettes de théorie des catégories s'appelle la catégorisation . Parfois, cela produit des résultats vraiment agréables et surprenants. Les physiciens ont commencé à dire que penser un groupe comme un gropoïde à un élément fait vraiment une grande différence . Je commence à réaliser que penser un monoïde comme une catégorie à un élément simplifie aussi beaucoup de choses. (Par exemple, une action monoïde est alors un foncteur dans Set . De telles choses forment des catégories et des topos cartésiens fermés. Donc, elles ont un calcul lambda et une logique intuitionniste aussi!)

Vous souhaitez classer les langues régulières. Je ne sais pas si cela a été fait, ou fait et trouvé sans intérêt. Je n'ai rien vu d'écrit à ce sujet. Cependant, la structure algébrique des langues régulières, les algèbres de Kleene, est suffisamment intéressante. Il existe une grande quantité de littérature à leur sujet. Mais, à mon avis, la théorie des langages réguliers et des automates finis souffre d'un engagement prématuré à la finitude. (Les groupes finis sont intéressants et importants, mais vous ne voulez pas que la définition de «groupe» s'engage au début dans la finitude.) Il serait donc utile de rejeter la finitude et d'étudier les structures plus généralement.

Le travail le plus intéressant actuellement en cours concerne les structures appelées bimonoïdes de localité définies par Hoare. Les algèbres concomitantes de Kleene se sont avérées en être un exemple . Les bimonoïdes locaux et la concurrence sont une direction de recherche active.

Uday Reddy
la source