Vers l'Institut Gaspard Monge
Vers le sommaire
Vers l'université de Marne-la-Vallée
Travaux de recherche

THEMES DE RECHERCHE ACTUELS

Reconnaissabilité par automates

La reconnaissabilité apporte une approche générale pour extraire des algèbres de Boole dans des familles de langages, comme par exemple celles de la hiérarchie de Chomsky, celles de la hiérarchie des langages indexés de Maslov, ou encore la famille des langages acceptés par les réseaux de Petri.

La reconnaissabilité a été définie par Eilenberg en 1967: une partie d'un monoïde est reconnue par morphisme inverse d'une partie d'un monoïde fini. Pour un monoïde donné, l'ensemble des parties reconnues forment une algèbre de Boole. Cette notion de reconnaissabilité a été étendue, notamment pour les termes, les graphes finis, les traces, les mots indexés par des ordres totaux.

La reconnaissabilité est ici considérée pour les automates, où un automate est un graphe (généralement infini) orienté et étiqueté par des lettres avec des sommets initiaux et des sommets finaux. On définit la reconnaissabilité par un automate H selon une famille F d'automates comme l'ensemble Rec(F,H) des langages acceptés par les automates de F qui s'appliquent morphiquement en H.

Si H est l'automate Boucles n'ayant qu'un seul état, qui est initial et final, et dont toute lettre étiquette une boucle, alors tout automate s'applique morphiquement en Boucles. Aussi, la famille Rec(F,Boucles) est l'ensemble des langages acceptés par les automates de F et qui n'est généralement pas une algèbre de Boole.

Pour obtenir des algèbres de Boole, on ajoute une condition, dite structurelle, sur les morphismes. Pour cela, on considère une famille R de relations binaires à laquelle on associe la famille F(R) des automates dont toute transition étiquetée est une relation de R.

On introduit la reconnaissabilité selon F(R) en restreignant les morphismes à être des relations de R, ce qui définit la sous-famille sRec(F,H) des langages acceptés par les automates de F qui s'appliquent morphiquement et structurellement en H.

La reconnaissabilité structurelle permet d'obtenir des algèbres de Boole pas seulement pour des automates à pile, ou à pile de piles, ... mais aussi en autorisant plusieurs piles. Précisément et pour tous entiers positifs m et n, on définit l'ensemble P(m,n) des relations binaires suffixes définissables par m piles de n niveaux de pile de piles. Pour tout automate non ambigü H de F(P(m,n)), la famille sRec(F(P(m,n),H) est une algèbre de Boole vis à vis du langage L(H) accepté par H (le langage L(H) - M est dans la famille lorsque M l'est). Ce résultat reste vrai si on restreint P(m,n) à la famille C(m,n) des relations suffixes sur m compteurs de niveau n. En particulier, C(m,1) correspond aux systèmes d'addition de vecteurs de dimension m. On obtient aussi des algèbres de Boole relativement à la famille des langages contextuels.

Cette reconnaissabilité structurelle est générale mais elle ne permet pas d'obtenir la famille des langages algébriques visibles (ou input-driven)..

Article: "Recognizability for automata" avec Didier Caucal, 22ième DLT (Developments in Language Theory), publication LNCS 11088, Springer, M. Hoshi, S. Seki (Eds.), 206-218 (2018).

Algèbres de Boole par reconnaissabilité par longueur

On vient d'indiquer que la reconnaissabilité structurelle ne permet pas d'obtenir l'algèbre de Boole des langages algébriques visibles. Une autre façon de reconnaïtre des algèbres de Boole est de se restreindre aux morphismes déterministes qui préservent la longueur. Pour cela, on ne considère que des automates dont les sommets sont des mots. Pour F une famille d'automates et H un automate de F, on définit la famille lRec(F,H) des langages acceptés par les automates de F qui s'appliquent en H par morphisme préservant la longueur. Pour la famille F des automates à pile et pour H non ambigü , lRec(F,H) est une algèbre de Boole (selon le langage L(H) accepté par H). Par contre, on n'a plus de fermeture par complémentaire pour la famille des automates à pile de piles pour des automates H déterministes. Au lieu de restreindre les familles F aux automates déterministes, on demande en plus aux morphismes d'être déterministes. Précisément, un morphisme f appliqué à un automate G est déterministe si on n'a pas deux sommets initiaux de G de même image par f, et si les buts de deux arcs de G de même source et de même étiquette n'ont pas la même image par f. On considère alors la sous-famille dlRec(F,H) des langages des automates G de F pour lesquels il existe un morphisme de G dans H qui soit à la fois déterministe et qui préserve la longueur des sommets.

On obtient que toute famille dlRec(F,H) est une algèbre de Boole (selon L(H)) sous deux hypothèses. La première hypothèse est que l'automate H soit non ambigü et longueur-déterministe: deux sommets initiaux ne sont pas de même longueur, et deux buts d'arcs de même source et étiquette sont de longueur différente. La deuxième hypothèse est que la famille F soit fermée par deux opérations habituelles pour les automates finis. On a le produit de synchronisation par longueur donnant la fermeture par intersection de dlRec(F,H). Pour la fermeture par complémentaire: L(H) - L(G), on a une opération de superposition par longueur de G sur H. Les algèbres de Boole dlRec(F,H) sont alors obtenues pour la famille F des automates à pile qui est fermée par synchronisation par longueur, et par superposition par longueur. On a en particulier la famille des langages algébriques visibles. Il en est de même pour la famille F des automates synchronisés et de différence de longueur bornée; ces automates reconnaissent les langages contextuels.