Automate à pile visible

En informatique théorique, et notamment en théorie des automates et des langages formels, un automate à pile visible (en anglais « visibly pushdown automaton ») est un automate à pile reconnaissant des mots sur un alphabet partitionné. Ils reconnaissent les langages à pile visible (en anglais « visibly pushdown languages »). Cette famille de langages est intermédiaire entre les langages rationnels et les langages algébriques déterministes.

Un mot imbriqué (en anglais « nested word »), 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 « nested word automata »). 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 leur applications.

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 $O(\log ^{2}n/\log \log n)$. Cette borne a été améliorée par von Braunmühl et Verbeek qui ont donné, pour la reconnaissance, une complexité $O(\log n)$ en espace et $O(n^{2}\log n)$ 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é NC¹.

Mot imbriqué

Relation de couplage

Une relation de couplage (en anglais « matching relation ») de longueur $\ell \geq 0$, aussi appelé une correspondance, est une relation binaire, partie du produit $\{-\infty ,1,2,\ldots ,\ell -1,\ell \}\times \{1,2,\ldots ,\ell -1,\ell ,\infty \}$, notée traditionnellement $\rightsquigarrow$. Les couples de cette relation sont appelées flèches. La relation vérifie les conditions suivantes :

1. si $i\rightsquigarrow j$ alors $i<j$ : toutes les flèches sont vers la droite ;
2. si $i_{1}\rightsquigarrow j$ et $i_{2}\rightsquigarrow j$ et $j<\infty$, alors $i_{1}=i_{2}$ : deux flèches n'aboutissent pas à la même position ;
3. si $i\rightsquigarrow j_{1}$ et $i\rightsquigarrow j_{2}$ et $i>-\infty$, alors $j_{1}=j_{2}$ : deux flèches ne commencent pas à la même position ;
4. si $i_{1}\rightsquigarrow j_{1}$ et $i_{2}\rightsquigarrow j_{2}$, alors on n'a pas $i_{1}<i_{2}<j_{1}<j_{2}$ : deux flèches ne se croisent pas.

Enfin, le couple $(-\infty ,\infty )$ n'est pas une flèche. Si $i\rightsquigarrow j$, alors

• $i$ est une position d'appel (en anglais « call position ») et
• $j$ est une position de retour (en anglais « return position ») ;
• si $i=-\infty$, alors $j$ est un retour pendant,
• si $j=\infty$, alors $i$ est un appel pendant (en anglais « pending call »)
• une position qui est ni d'appel ni de retour est une position interne (en anglais « internal position ».

Un couple $(i,j)$ dont aucun des deux indices n'est pendant est bien parenthésé (en anglais « well matched »).

Mot imbriqué

Un mot imbriqué de longueur $\ell$ sur un alphabet $\Sigma$ est une couple $(w,\rightsquigarrow )$, où $w$ est un mot de longueur $\ell$ sur $\Sigma$ , dans le sens usuel du terme, et où $\rightsquigarrow$ est une relation de couplage de longueur $\ell$.

Exemples

1. La relation $\rightsquigarrow =\{(-\infty ,1),(2,\infty ),(3,4),(5,7),(8,\infty )\}$ définit les positions d'appel $-\infty$, 2,3,5, 8, et les positions de retour $\infty$, 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 $3^{n}$ relations de couplage de longueur $n$

Codage de mots imbriqués par des mots ordinaires

Alphabet structuré

Les mots imbriqués sur un alphabet $\Sigma$ peuvent être codés comme mots ordinaires sur un alphabet augmenté, appelé alphabet structuré noté ${\hat {\Sigma }}$ ; chaque symbole $a$ de $\Sigma$ 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 $\Sigma$ est composé de symboles $\langle a$ (pour $a$ en position d'appel), $a\rangle$ (pour a $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

$w=abaabccca$

et la relation de couplage

$\rightsquigarrow =\{(-\infty ,1),(2,\infty ),(3,4),(5,7),(8,\infty )\}$

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

$a\rangle \langle b\langle aa\rangle \langle bcc\rangle ca$

Automates

Les automates de mots imbriques 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é $(w,\rightsquigarrow )$, 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 $Q$ d'états dits linéaires
• un état initial (linéaire) $q_{0}\in Q$
• un ensemble d'états terminaux (linéaires) $Q_{f}\subseteq Q$
• un ensemble fini $P$ d'états dits hiérarchiques
• un état initial (hiérarchique) $p_{0}\in P$
• un ensemble d'états terminaux (hiérarchiques) $P_{f}\subseteq P$

et trois fonctions de transition, une pour chaque type de symbole

• une fonction de transitions d'appels $\delta _{c}:Q\times \Sigma \to Q\times P$
• une fonction de transitions internes $\delta _{i}:Q\times \Sigma \to Q$
• une fonction de transitions de retours $\delta _{r}:Q\times P\times \Sigma \to Q$

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 « run ») sur un mot imbriqué $a_{1}a_{2}\cdots a_{n}$ est une suite $q_{0},q_{1},\ldots ,q_{n}$ d'états linéaires et une suite d'états hiérarchiques $p_{i}\in P$, un pour chaque position d'appel et correspondants aux flèches du couplage, telles que

• si $i$ est une position d'appel, $\delta _{c}(q_{i-1},a_{i})=(q_{i},p_{i})$ ;
• si $i$ est une position interne, $\delta _{i}(q_{i-1},a_{i})=q_{i}$ ;
• si $i$ est une position de retour et $j$ est le prédécesseur d'appel de $i$, alors $\delta _{r}(q_{i-1},p_{j},a_{i})=q_{i}$, et si $i$ est un retour pendant, alors $\delta _{r}(q_{i-1},p_{0},a_{i})=q_{i}$.

L'automate accepte le mot imbriqué si le dernier état est un état final : $q_{n}\in Q_{f}$.

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 $M=(Q,{\hat {\Sigma }},\Gamma ,\delta ,q_{0},F)$ comporte :

• $Q$ un ensemble fini d'états ;
• $q_{0}\in \,Q$ est l’état initial, et
• $F\subseteq Q$ est l'ensemble des états d'acceptation ;
• ${\hat {\Sigma }}$ un alphabet structuré, partitionné en trois ensembles $\Sigma _{c}$, $\Sigma _{r}$, et $\Sigma _{i}$. L'alphabet $\Sigma _{c}$ contient les symboles d'appel, $\Sigma _{r}$ les symboles de retour, et enfin $\Sigma _{i}$ les symboles internes ;
• $\Gamma$ est un ensemble fini, l'alphabet de pile, avec un symbole particulier $\bot \in \Gamma$ de fond de pile ;
• $\delta =\delta _{c}\cup \delta _{r}\cup \delta _{i}$ est la fonction de transition, elle-même partitionnée en trois parties correspondant aux transitions d'appel, internes et de retour, à savoir :
  • $\delta _{c}:Q\times \Sigma _{c}\to Q\times \Gamma \setminus \{\bot \}$, la fonction de transition d'appel : le fond de pile ne peut être empilé à nouveau ;
  • $\delta _{r}:Q\times \Sigma _{r}\times \Gamma \to Q$, la fonction de transition de retour ;
  • $\delta _{i}:Q\times \Sigma _{i}\to Q$, la fonction de transition interne ;

La notion de calcul pour un automate à pile visible est une restriction et en même temps une variation de celle des automate à pile. La restriction porte sur le choix des opérations : quand un automate à pile visible lit une lettre $a$, il peut empiler un symbole seulement si c'est une lettre d'appel de $\Sigma _{c}$, dépiler seulement si c'est une lettre de $\Sigma _{r}$, enfin si $a\in \Sigma _{i}$ il ne peut pas modifier la pile. La modification porte sur la forme des opérations de pile : dans un automate à pile usuel, l'empilement éventuel est toujours précédé d'un dépilement, alors qu'ici, les deux opérations sont séparées. De plus, quand il y a empilement, on n'empile qu'un seul symbole sur la pile. Un calcul acceptant est un calcul qui se termine en un état d'acceptation.

Un automate à pile visible ne peut pas empiler et dépiler avec le même symbole d'entrée. Par conséquent, des langages comme

$L=\{a^{n}ba^{n}\mid n\in \mathbb {N} \}$

ne sont pas acceptés par des automates à pile visible, alors qu'ils peuvent l'être par un automate à pile déterministe usuel.

Les automates à pile visible non déterministes peuvent être déterminisés, comme c'est le cas pour les automates finis ; ceci les distingue des automates à pile usuels. Toutefois, la procédure de déterminisation, partant d'un automate non déterministe à $s$ états, peut conduire à un automate déterministe ayant jusqu'à $2^{s^{2}}$ états.

Problèmes de décisions et complexité

Soit $|A|$ la taille d'une description d'un automate $A$. On peut teste l'acceptation d'un mot de longueur n par l'automate en temps $O(|A|^{3}n)$. En particulier, on peut tester si le langage est vide en temps $O(|A|^{3})$. Pour deux automates non déterministes $A$ et $B$, décider si l’ensemble des mots acceptés par $A$ est un sous-ensemble des mots acceptés par $B$ est EXPTIME-complet. Il est aussi EXPTIME-complet de savoir s'il existe un mot qui n'est pas accepté.

Complexité de problèmes de décision pour les automates

	vide	universalité équivalence	inclusion
automates finis déterministes	Nlogspace	Nlogspace	Nlogspace
automates finis non déterministes	Nlogspace	Pspace	Pspace
automates à pile	Ptime	indécidable	indécidable
automates à pile déterministes	Ptime	décidable	indécidable
automates de mots imbriqués déterministes	Ptime	Ptime	Ptime
automates de mots imbriqués non déterministes	Ptime	Exptime	Exptime

Langages

Les automates à pile visible déterministes peuvent être vus comme des automates à pile déterministes particuliers ; ainsi, la famille des langages à pile visible sur un alphabet $\,{\hat {\Sigma }}$ donné est un sous-ensemble de la famille des langages algébriques déterministes sur $\,{\hat {\Sigma }}$. En particulier, la fonction qui efface la relation de couplage des mots imbriqués transforme des langages de mots imbriqués en langages algébriques.

Propriétés de fermeture

La famille des langages à pile visible sur un même alphabet structuré est fermée pour les opérations suivantes :

• union
• intersection
• complément,
• étoile de Kleene
• concaténation
• image miroir
• préfixe, suffixe, facteur.

La famille est donc une algèbre de Boole et de plus une famille rationnellement fermée de langages. De plus l'ensemble des préfixes d'un langage à pile visible l'est encore, et par image miroir aussi l'ensemble des suffixes (les suffixes sont les retournés des préfixes de l'image miroir), et donc aussi l'ensemble des facteurs.

En ce qui concerne la complémentation, la construction usuelle pour les automates à pile déterministes s'étend simplement aux automates à pile visible. Ceci n'est pas le cas pour l’intersection, puisque les langages algébriques déterministes ne sont pas fermés par intersection, et une construction spécifique doit être réalisée. Une preuve simple de la fermeture par complémentation est au moyen des automates de mots imbriqués : il suffit d'échanger les états terminaux et non terminaux.

D'autres propriétés de fermeture, comme l'insertion ou la suppression de facteurs dans un mot, ont été étudiées par Alexander Okhotin et Kai Salomaa.

Complexité des opérations

Alur et Madhusudan ont prouvé les diverses propriétés de clôture des langages rapportés plus haut, et évalué la complexité du test de savoir si le langage est vide. Ils ont aussi prouvé que la simulation d’un automate non déterministe à $n$ états par un automate déterministe équivalent peut demander, dans le pire des cas, $2^{\Theta (n^{2})}$ états. Un article d’Alexander Okhotin et Kai Salomaa donne des constructions efficaces pour la concaténation l’étoile de Kleene et l’image miroir (ou transposition). Ils montrent que l’étoile et le transposé d’un automate à pile visible avec $n$ états peuvent être construit avec $2^{O(n\log n)}$ états, assez proche d’une borne inférieure donnée antérieurement par Piao et Salomaa et qui est $2^{\Omega (n\log n)}$. Quant à la concaténation, une construction de Okhotin et Salomaa pour concaténer deux automates, l'un à $n$ et l'autre à $m$ états donne un automate de $m2^{O(n\log n)}$ états, et une borne inférieure en $m2^{\Omega (n\log n)}$.

La table suivante est extraite de l'article d'Okhotin et Salomaa. Elle contient les bornes connues en 2017 pour la complexité des opérations pour les automates finis déterministes (DFA), inambigus (UFA), non déterministes(NFA), à pile visible déterministes (IDPFA) et non déterministes (NIDPDA) :

Complexité des opérations de fermeture

	DFA	UFA	NFA	IDPDA	NIDPDA
union	$mn$	$mn+m+n\leq \cdot \leq m+O(n2^{0.79m})$	$m+n+1$	$\Theta (mn)$	$m+n+O(1)$
intersection	$mn$	$mn$	$mn$	$\Theta (mn)$	$\Theta (mn)$
complément	$n$	$n^{2-o(1)}\leq \cdot \leq O(2^{0.79n})$	$2^{n}$	$n$	$2^{\Theta (n^{2})}$
produit	$m2^{n}-2^{n-1}$	$3/42^{m+n}-1$	$m+n$	$m2^{\Theta (n\log n)}$	$m+n+O(1)$
carré	$n2^{n}-2^{n-1}$	?	$2n$	$2^{\Theta (n\log n)}$	$n+O(1)$
étoile	$3/4\cdot 2^{n}$	$(n-1)^{2}\leq \cdot \leq 3/4\cdot 2^{n}$	$n+1$	$2^{\Theta (n\log n)}$	$n+O(1)$
miroir	$2^{n}$	$n$	$n+1$	$2^{\Theta (n\log n)}$	$n+O(1)$

Relation avec d'autres classes de langages

Alur et Madhusudan montrent que les langages à pile visible sont plus généraux que les langages à parenthèses (en anglais « parenthesis languages ») décrits en 1967 par McNaughton, puis étendus. En 2012, Crespi Reghizzi et Mandrioli montrent que les langages à pile visible sont strictement contenus dans la classe des langages décrits par grammaire à précédence d'opérateurs, introduits par Floyd en 1963 et qui ont les mêmes propriétés de clôture. Voici une table, tirée des articles d'Alur et Madhusudan et de Crespi Reghizzi et Mandrioli, qui situe les langages à pile visible et leurs propriétés de clôture dans la hiérarchie de Chomsky.

Propriétés de fermeture

Langages	union	intersection	complément	produit étoile	préfixe suffixe	miroir
rationnels	oui	oui	oui	oui	oui	oui
équilibrés	oui	oui	non	oui	non	oui
à pile visible	oui	oui	oui	oui	oui	oui
Floyd	oui	oui	oui	oui	oui	oui
déterministes	non	non	oui	non	oui	non
algébriques	oui	non	non	oui	oui	oui

Autres modèles de description

Grammaires à pile visible

Les langages à pile visible sont exactement les langages que l'on peut engendrer avec une famille de grammaires appelées grammaires à pile visible (en anglais visibly pushdown grammars). Ces grammaires sont définies comme une restriction des grammaires algébriques. Une grammaire à pile visible est 4-uplet

$G=(V,\Sigma ,R,S)$ où

• $V=V^{0}\cup V^{1}$, l'ensemble des variables est l'union disjointe de deux ensembles $V^{0}$ et $V^{1}$. Les langages engendrés par des variables de $V^{0}$ sont composés de mots sans éléments pendants, ceux engendrés par .
• $\Sigma$ est l'alphabet terminal, mais les règles comportent des lettres de l’alphabet structuré.
• $R$ est l'ensemble des règles ou productions de la grammaire. Les règles sont de trois sortes, avec $X,Y\in V,Z\in V^{0}$ :
  • $X\to \varepsilon$
  • $X\to aY$ avec $a\in {\hat {\Sigma }}$ et, si $X\in V^{0}$, alors $a\in \Sigma$ et $Y\in V^{0}$
  • $X\to \langle aYb\rangle Z$ avec $a,b\in \Sigma ,\,Y\in V^{0}$ et, si $X\in V^{0}$ alors $Z\in V^{0}$
• $S\in V\,$ est l'axiome.

Les variables de $V^{0}$ n'engendres que des langages de mots bien parenthésés, sans appel ou retour pendant, alors que les mots engendrés par des variables de $V^{1}$ contiennent des appels ou des retours pendants.

Dans une règle $X\to aY$, si $a$ est en position d'appel ou de retour, alors ou bien c’est un lettre qui n’est pas couplée ou sa lettre couplée n’est pas mémorisée, et par conséquent $X$ doit être dans $V^{1}$.

Dans une règle $X\to \langle aYb\rangle Z$, les positions correspondant aux symboles $a$ et $b$ forment un couple parenthésé, avec entre elles un mot bien parenthésé engendré par $Y\in V^{0}$, et si $X$ engendre des mots bien parenthésés, cette propriété se propage à $Z$.

On peut montrer qu’un langage de mots imbriqués est engendrée par une grammaire à pile visible et réciproquement.

Circuits booléens uniformes

Le problème de décider si un mot de longueur $\ell$ est acceptée par un automate de mots imbriqués donné peut être résolu par une par un circuit booléen uniforme de profondeur $\mathrm {O} (\log \ell )$.

Description logique

Les langages réguliers de mots imbriqués sont exactement les langages décrits par la logique monadique du second ordre avec les deux prédicats unaires call et return, la fonction successeur et la relation de couplage ↝ : les formules sont

${\begin{aligned}\varphi :=&a(x)\mid X(x)\mid {\mathsf {call}}(x)\mid {\mathsf {ret}}(x)\mid x=y+1\mid x\rightsquigarrow y\\&\mid \varphi \lor \varphi \mid \varphi \land \varphi \mid \lnot \varphi \mid \exists x.\varphi \mid \forall x.\varphi \end{aligned}}$

où $a\in \Sigma$, $x,y$ sont des variables du premier ordre et $X$ du second ordre.

Extension : transducteur à pile visible

Les transducteurs à pile visible, dont la théorie est détaillée par Filiot, Raskin, Reynier, Servais et Talbot, permettent notamment de modéliser des transformations de mots imbriqués en mots. Ils ont de bonnes propriétés algorithmiques, comme la décidabilité de l'équivalence des fonctions réalisées, et sont fermés par look-ahead « régulier ».

Les transducteurs à pile visible étendent les automates à pile visible avec des sorties. Ils lisent des mots imbriqués, et produisent des mots de sortie qui ne sont pas nécessairement imbriqués. Comme pour les automates à pile visible, le comportement de la pile est synchronisé avec les types de symboles d'entrée : lors de la lecture d'un symbole d'appel, exactement un symbole de pile est ajouté au sommet de la pile ; lors de la lecture d'un symbole de retour, exactement un symbole de pile est supprimé au sommet de la pile ; et la pile n'est pas modifiée lors de la lecture des symboles internes. Durant leurs transitions, les transducteurs peuvent ajouter des mots sur leur bande de sortie ; leur concaténation définit le mot de sortie résultant. Par conséquent, transducteurs à pile visible définissent des transformations des mots imbriqués en mots et peuvent être vus comme une sous-classe de transducteurs à pile.

Les transducteurs à pile visible jouissent de propriétés de clôture similaires à celles des transducteurs finis : ils sont clos par union, mais ni par intersection ni par complément. À la différence des transducteurs usuels, les transducteurs à pile visible ne sont pas fermés par composition, sauf pour des cas particuliers.

Une des propriétés importantes à vérifier est l'équivalence, c'est-à-dire la propriété que deux transducteurs donnés définissent la même relation. L'équivalence est indécidable pour les transducteurs finis usuels ; elle est en revanche décidable pour des transducteurs à images bornées, c'est-à-dire tels que l'image de tout mot a au plus k éléments, pour un entier k fixe. Pour des transducteurs à pile visible à images bornées, la même propriété est encore ouverte ; pour des transducteurs à pile visible fonctionnels en revanche, la propriété est décidable, et le problème de décision est EXPTIME-complet.

Références bibliographiques

• [Alur Madhusudan 2004] Rajeev Alur et Parthasarathy Madhusudan, « Visibly pushdown languages », dans Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04, 2004 (ISBN 1581138520, DOI 10.1145/1007352.1007390, lire en ligne), p. 202–211
• [Alur Madhusudan 2009] (en) Rajeev Alur et Parthasarathy Madhusudan, « Adding nesting structure to words », Journal of the ACM, vol. 56, n^o 3,‎ 2009, p. 1–43 (DOI 10.1145/1516512.1516518, lire en ligne)
• [Floyd 1963] (en) Robert W. Floyd, « Syntactic Analysis and Operator Precedence », Journal of the ACM, vol. 10, n^o 3,‎ juillet 1963, p. 316–333 (DOI 10.1145/321172.321179)
• [McNaughton 1967] (en) R. McNaughton, « Parenthesis Grammars », Journal of the ACM, vol. 14, n^o 3,‎ 1967, p. 490 (DOI 10.1145/321406.321411)
• [Alur et al. 2008] (en) R. Alur, M. Arenas, P. Barcelo, K. Etessami, N. Immerman et L. Libkin, « First-Order and Temporal Logics for Nested Words », Logical Methods in Computer Science, vol. 4, n^o 4,‎ 2008 (DOI 10.2168/LMCS-4(4:11)2008, arXiv 0811.0537)
• [Crespi Reghizzi, Mandrioli 2012] (en) Stefano Crespi Reghizzi et Dino Mandrioli, « Operator precedence and the visibly pushdown property », Journal of Computer and System Sciences, vol. 78, n^o 6,‎ 2012, p. 1837–1867 (DOI 10.1016/j.jcss.2011.12.006, lire en ligne).
• [Lonati, Mandrioli, Panella, Pradella 2015] (en) Violetta Lonati, Dino Mandrioli, Federica Panella et Matteo Pradella, « Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization », SIAM Journal on Computing, vol. 44, n^o 4,‎ 2015 (DOI 10.1137/140978818).
• [Braunmühl, Verbeek 1985] (en) Burchard von Braunmühl et Rutger Verbeek, « Input Driven Languages are Recognized in log n Space », North-Holland Mathematics Studies, vol. 102, n^o C,‎ 1985, p. 1–19 (ISSN 0304-0208, DOI 10.1016/S0304-0208(08)73072-X).
• [Dymond 1988] (en) Patrick W. Dymond, « Input-driven languages are in log n depth », Information Processing Letters, vol. 26, n^o 5,‎ 1988, p. 247–250 (ISSN 0020-0190, DOI 10.1016/0020-0190(88)90148-2).
• [Mehlhorn 1980] Kurt Mehlhorn, « Pebbling mountain ranges and its application to DCFL-recognition », dans J. Bakker et J. van Leeuwen (éditeurs), Automata, Languages and Programming. ICALP 1980., Springer, coll. « Lecture Notes in Computer Science, vol 85 », 1980 (ISSN 0302-9743, DOI 10.1007/3-540-10003-2_89), p. 422–435.
• [Piao, Salomaa 2009] (en) Xiaoxue Piao et Kai Salomaa, « Operational state complexity of nested word automata », Theoretical Computer Science, vol. 410, n^o 35,‎ 2009, p. 3290–3302 (ISSN 0304-3975, DOI 10.1016/j.tcs.2009.05.002).
• [Okhotin Salomaa 2017] (en) Alexander Okhotin et Kai Salomaa, « State complexity of operations on input-driven pushdown automata », Journal of Computer and System Sciences, vol. 86,‎ 2017, p. 207–228 (ISSN 0022-0000, DOI 10.1016/j.jcss.2017.02.001).
• [Okhotin Salomaa 2019] Alexander Okhotin et Kai Salomaa, « Further closure properties of input-driven pushdown automata », Theoretical Computer Science, vol. 798,‎ 2019, p. 65–77 (ISSN 0304-3975, DOI 10.1016/j.tcs.2019.04.006)
• [Filiot, Raskin, Reynier, Servais 2018] Emmanuel Filiot, Jean-François Raskin, Pierre-Alain Reynier, Frédéric Servais et Jean-Marc Talbot, « Visibly pushdown transducers », Journal of Computer and System Sciences, vol. 97,‎ 2018, p. 147-181 (DOI 10.1016/j.jcss.2018.05.002).
• [Caralp, Reynier, Talbot 2015] Mathieu Caralp, Pierre-Alain Reynier et Jean-Marc Talbot, « Trimming visibly pushdown automata », Theoretical Computer Science, vol. 578,‎ 2015, p. 13–29 (DOI 10.1016/j.tcs.2015.01.018).
• [Sakharov 2020] Alexander Sakharov, « Annotated regular expressions and input-driven languages », Information Processing Letters, vol. 159-160,‎ 2020, article n^o 105958 (DOI 10.1016/j.ipl.2020.105958).

• (en) John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979, 418 p. (ISBN 978-0-201-02988-8).

Articles liés

• Vérification de modèles

Liens externes

• Rajeev Alur, « Nested words aka Visibly Pushdown Languages ».
• Classe VPL sur le Complexity Zoo
• Christian Schilling, « Nested Word Automata », Automata Theory, sur swt.informatik.uni-freiburg.de, Université de Fribourg, Sommersemester 2012 (consulté le 25 février 2017).