En informatique théorique, et notamment en théorie des automates et des langages formels, un automate à pile visible (en anglais ) est un automate à pile reconnaissant des mots sur un alphabet partitionné. Ils reconnaissent les langages à pile visible (en anglais ). Cette famille de langages est intermédiaire entre les langages rationnels et les langages algébriques déterministes.
Un mot imbriqué (en anglais ), notion proposée par Rajeev Alur et Parthasarathy Madhusudan, est un objet doté d'une double structure : d'un côté, c'est une chaîne de caractères, comme dans l’usage traditionnel de la modélisation de structures totalement ordonnées, d'un autre côté, c'est un modèle de structure hiérarchique, comme les arbres enracinés ou les systèmes de parenthèses emboîtées. Les automates acceptant des ensembles de mots imbriqués sont les automates de mots imbriqués (en anglais ). Ce sont des automates généralisant les automates finis de mots. Le codage par système de parenthèses de mots imbriqués redonne la classe des langages à pile visible.
Depuis l'introduction de cette terminologie par Alur et Madhusudan en 2004, suivie d'un développement autour de ces notions en 2009, ces concepts ont déclenché un nombre important de recherches sur et autour de ces objets et de leurs applicationsRecherche de Google Scholar pour ou ..
Description et motivation
Description informelle Les mots imbriqués sont un modèle pour la représentation de données avec à la fois un ordre linéaire et un couplage hiérarchique des éléments.. Des exemples de données avec cette double structure hiérarchique et linéaire incluent les exécutions de programmes structurés, des données linguistiques annotées et des documents HTML ou XML. Un mot imbriqué se compose d'une séquence de positions linéairement ordonnées, augmentée d'arcs d'imbrication reliant des appels à des retours (ou des balises ouvrantes à des balises fermantes). Les arcs ne se croisent pas dans une structure hiérarchique correctement imbriquée, mais on autorise des arcs non couplés. Cette structure d'imbrication peut être représentée de manière unique par une séquence spécifiant les types de positions (appels, retours et internes). Les mots imbriqués généralisent à la fois les mots et les arbres ordonnés, et permettent les opérations sur les mots et sur les arbres.
Les automates de mots imbriqués sont des automates finis acceptant des mots imbriqués ; ils définissent la classe des langages rationnels (ou réguliers) des mots imbriqués.
Pour un langage L donné de mots imbriqués sur un alphabet, un codage linéaire des mots imbriqués donne un langage L sur l'alphabet marqué composé de symboles marqués avec le type de la position. Si L est un langage rationnel de mots imbriqués, alors L est un langage algébrique. En fait, il est accepté par un automate à pile particulier appelé automate à pile visible ; la classe des langages de mots qu'ils acceptent sont des langages à pile visible. Ce sont tous de langages algébriques déterministes particuliers qui se classent entre les langages équilibrés et les langages de Floyd, engendrés par des grammaires à précédence d'opérateurs.
Applications Les langages rationnels de mots imbriqués s'emploient avantageusement dans la vérification algorithmique des programmes structurés, car au lieu de considérer un programme comme un langage algébrique de mots, le considérer comme un langage régulier de mots imbriqués (ou équivalent, comme un langage à pile visible), permet la vérification de nombreuses propriétés (telles que l'inspection de la pile, les pré et postconditions) qui ne sont pas exprimables dans les logiques de spécification existantes.
Les données qui possèdent un double structure, à la fois linéaire et hiérarchique, sont traditionnellement modélisées à l'aide d'arbres ordonnés, et elles sont interrogées à l'aide d'automates arborescents. Dans les arbres ordonnés, les nœuds de même parent sont ordonnés linéairement, et les parcours d'arbre classiques tels que le parcours infixe (ou le parcours en profondeur de gauche à droite) peuvent être utilisés pour définir un ordre implicite sur les nœuds.
Pour le traitement des documents, les mots imbriqués ont de nombreux avantages sur les arbres ordonnés. La représentation par arbre suppose implicitement que les données linéaires peuvent être analysés dans un arbre ; on ne peut donc pas traiter des données qui ne peuvent pas être représenter correctement. Des opérations sur les mots comme la prise des préfixes, des suffixes, et la concaténation, sont naturelles en traitement des documents et n'ont pas d'analogues dans les arbres. Pareillement, les automates d'arbre peuvent difficilement exprimer des contraintes qui font référence à l'ordre linéaire dans sa totalité. Par exemple, une requête demandant que des modèles apparaissent dans un ordre donné à l'intérieur d'un document se vérifie par un automate de mots ordinaires en temps linéaire, mais requiert un temps exponentiel dans un automate d'arbre ascendant. Cet exemple montre que certaines requêtes peuvent être codées de façon plus succincte dans un automate de mots imbriqués qui lit le mot de gauche à droite et traite les liens d'imbrication au fur et à mesure qu'ils apparaissent. Ceci correspond à des logiciels de fouille de flots de données, comme ils servent dans les logiciels pour XML.
Note historique
Les automates à pile visible ont été introduits, avant Alur et Madhusudan, sous le nom de « input-driven pushdown automata » par Kurt Mehlhorn dans les années 1980. ; il a démontré qu’un langage défini par un tel automate peut être reconnu en temps polynomial, et avec un espace . Cette borne a été améliorée par von Braunmühl et Verbeek. qui ont donné, pour la reconnaissance, une complexité en espace et en temps. Ces auteurs ont fait une autre contribution importante en montrant que les variantes déterministe et non déterministe du modèle reconnaissent les mêmes langages. Ultérieurement, Dymond. a montré que cette famille de langages est contenue dans la classe de complexité NC1.
Mot imbriqué
Relation de couplage Une relation de couplage (en anglais ) de longueur , aussi appelé une correspondance, est une relation binaire, partie du produit , notée traditionnellement . Les couples de cette relation sont appelées flèches. La relation vérifie les conditions suivantes : si alors : toutes les flèches sont vers la droite ; si et et , alors : deux flèches n'aboutissent pas à la même position ; si et et , alors : deux flèches ne commencent pas à la même position ; si et , alors on n'a pas : deux flèches ne se croisent pas. Enfin, le couple n'est pas une flèche. Si , alors est une position d'appel (en anglais ) et est une position de retour (en anglais ) ; si , alors est un retour pendant, si , alors est un appel pendant (en anglais ) une position qui est ni d'appel ni de retour est une position interne (en anglais . Un couple dont aucun des deux indices n'est pendant est bien parenthésé (en anglais ). Mot imbriqué Un mot imbriqué de longueur sur un alphabet est une couple , où est un mot de longueur sur , dans le sens usuel du terme, et où est une relation de couplage de longueur .
Exemples 1. La relation définit les positions d'appel , 2,3,5, 8, et les positions de retour , encore que les deux infinis peuvent ne pas être comptés dans les positions ; les positions 1, 2 et 8 sont pendantes, la position 6 est interne, les couples (3,4) et (5,7) sont bien parenthésés. Une façon de présenter la nature des positions est une suite de c (call), r (retour), et i (interne) selon le type rencontré ; ainsi, la relation ci-dessus se décrit par : r c c r c i r c
2. La suite r c r r c i c i ne contient qu'un seul couple bien parenthésé, le couple (2,3) ; 1 et 4 sont de positions de retour pendantes, et 5 et 7 des positions d'appel pendantes.
3. Le mot i c i c i i r r i ne contient aucune position pendante.
La représentation des relations de couplage par des mots montre qu'il y a relations de couplage de longueur .
Codage de mots imbriqués par des mots ordinaires Alphabet structuré Les mots imbriqués sur un alphabet peuvent être codés comme mots ordinaires sur un alphabet augmenté, appelé alphabet structuré noté ; chaque symbole de est présenté en trois exemplaires, le premier quand il figure, dans un mot imbriqué, en position d'appel, le deux quand il est en position de retour, le troisième enfin quand il figure en position interne. L'alphabet est composé de symboles (pour en position d'appel), (pour a en position de retour) et de a lui-même quand il est en position interne. L'alphabet triple donc de taille. Cette écriture revient donc à superposer un mot ordinaire avec la séquence des i c r introduits plus haut.
Exemple Pour le mot
et la relation de couplage
qui est aussi représentée par la séquence r c c r c i r c i le codage sur l'alphabet structuré est
Automates Les automates de mots imbriquesTerminologie utilisée par exemple dans Grégoire Laurence, Normalisation et Apprentissage de Transductions d’Arbres en Mots. Thèse de l'Université des Sciences et Technologie de Lille - Lille I, 2014. sont des automates qui opèrent, presque comme des automates finis usuels, sur les mots imbriqués, alors que les automates à pile visible sont des automates à pile qui opèrent sur le codage des mots sur l'alphabet structuré.
Automate de mots imbriqués Un automate de mots imbriqués a un nombre fini d'états, et opère presque comme un automate fini déterministe sur les mots usuels, où les lettres sont lues de gauche à droite et où l'état courant dépend de l'état précédent et de la lettre lue ; dans un automate de mots imbriqués, à la lecture d'une lettre d'un mot imbriqué , le comportement varie en fonction de nature de la position de la lettre lue ; en plus des états ordinaires, l'automate possède des états hiérarchiques qui se propagent depuis une position d'appel et dont l'automate tient compte au moment de la position de retour correspondante. Un langage reconnu par un automate de mots imbriqués est un langage régulier ou rationnel de mots imbriqués.
De manière formelle, un automate de mots imbriqué comporte un ensemble fini d'états dits linéaires un état initial (linéaire) un ensemble d'états terminaux (linéaires) un ensemble fini d'états dits hiérarchiques un état initial (hiérarchique) un ensemble d'états terminaux (hiérarchiques) et trois fonctions de transition, une pour chaque type de symbole une fonction de transitions d'appels une fonction de transitions internes une fonction de transitions de retours Un automate démarre dans l'état initial, et lit le mot imbriqué dans l'ordre linéaire des lettres. Quand il rencontre une lettre d'appel, l'automate propage un état hiérarchique le long de la flèche sortante. Cet état hiérarchique est récupéré lorsque l'automate lit la lettre de retour correspondante.
Formellement, un calcul (en anglais ) sur un mot imbriqué est une suite d'états linéaires et une suite d'états hiérarchiques , un pour chaque position d'appel et correspondants aux flèches du couplage, telles que si est une position d'appel, ; si est une position interne, ; si est une position de retour et est le prédécesseur d'appel de , alors , et si est un retour pendant, alors . L'automate accepte le mot imbriqué si le dernier état est un état final : .
Les automates peuvent être aussi non déterministes, et avoir alors plusieurs états initiaux.
Automate à pile visible
Un automate à pile visible déterministe est un automate à pile déterministe particulier, où l'alphabet des données est partitionné en trois parties, chacune déterminant la nature des opérations de pile.
Formellement, un automate à pile visible déterministe comporte : un ensemble fini d'états ; est l’état initial, et est l'ensemble des états d'acceptation ;