Automate fini alternant

Il existe plusieurs classes d’automates finis qui diffèrent par leur « type de branchement » : les automates déterministes, automates non déterministes, les automates universels et automates alternants. Un automate déterministe traite un mot ${\displaystyle w=a_{1}a_{2}\cdots a_{k}}$ en passant d’un état au suivant selon la fonction de transition. L’automate accepte le mot ${\displaystyle w}$ à partir d’un état ${\displaystyle q}$ si l’état atteint après la lecture de ${\displaystyle a_{1}}$ accepte le suffixe ${\displaystyle v=a_{2}\cdots a_{k}}$. Un automate non déterministe qui lit la lettre ${\displaystyle a}$ dans un état ${\displaystyle q}$ peut en revanche passer en plusieurs états, déterminés par la relation de transition. L’automate accepte ${\displaystyle w}$ à partir de ${\displaystyle q}$ si l’un des états ${\displaystyle q_{1},\ldots ,q_{m}}$ dans lesquels il peut passer après la lecture de ${\displaystyle a_{1}}$ accepte le suffixe ${\displaystyle v}$. Une notion duale est celle d’automate universel. Comme pour un automate non déterministe, la relation de transition donne, pour un état ${\displaystyle q}$ et une lettre ${\displaystyle a}$, un ensemble d’états; mais l’interprétation est ici que ${\displaystyle w}$ est accepté depuis l’état ${\displaystyle q}$ si tous les états ${\displaystyle q_{1},\ldots ,q_{m}}$ atteints après la lecture de ${\displaystyle a_{1}}$ acceptent le suffixe ${\displaystyle v}$.

Les automates alternants généralisent à la fois les automates non déterministes et les automates universels. Ils délèguent le rôle de tester l’acceptation du suffixe d'un mot à plusieurs états, en combinant leurs résultats par des conjonctions et disjonctions. Par exemple, une transition qui de l'état ${\displaystyle q}$, en lisant la lettre ${\displaystyle a}$, va vers l'expression ${\displaystyle q_{1}\lor (q_{2}\land q_{3})}$ , stipule que le mot ${\displaystyle w=av}$ est accepté depuis ${\displaystyle q}$ si son suffixe ${\displaystyle v}$ est accepté depuis ${\displaystyle q_{1}}$ ou à la fois depuis ${\displaystyle q_{2}}$ et ${\displaystyle q_{3}}$.

Un automate fini alternant ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,q_{0},F,g)}$ est composé des données suivantes :

• ${\displaystyle Q}$ un ensemble fini d'états ;
• ${\displaystyle \Sigma }$ un alphabet d'entrée ;
• ${\displaystyle F\subseteq Q}$ un ensemble d'états terminaux ;
• ${\displaystyle h:2^{Q}\to \{0,1\}}$, une fonction d'acceptation ;
• ${\displaystyle g\colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}}$ une fonction de transition.

L'état initial usuel dans les automates est remplacé par la fonction d'acceptation ${\displaystyle h}$[1]. La fonction de transition ${\displaystyle g}$ associe à un état ${\displaystyle q}$, à une lettre ${\displaystyle a}$ et à un vecteur d'états ${\displaystyle v}$ indicé par ${\displaystyle Q}$, une valeur booléenne. La fonction ${\displaystyle g}$ est étendue au mots par les deux propriétés suivantes :

• ${\displaystyle g(q,\varepsilon ,v)=v_{q}}$, où ${\displaystyle v_{q}}$ est la coordonnée d'indice ${\displaystyle q}$ de ${\displaystyle v}$.
• ${\displaystyle g(q,ax,v)=g(q,a,g(x,v))}$, où ${\displaystyle g(x,v)}$ est le vecteur ${\displaystyle g(q,x,v)_{q\in Q}}$.

Vue comme fonction opérant sur les vecteurs d'états, la fonction ${\displaystyle g:\Sigma ^{*}\times \{0,1\}^{Q}\to \{0,1\}^{Q}}$ est donc étendue par

${\displaystyle g(\varepsilon ,v)=v}$

${\displaystyle g(ax,v)=g(a,g(x,v))}$

L'ensemble des mots acceptés par ${\displaystyle {\mathcal {A}}}$ est

${\displaystyle L({\mathcal {A}})=\{w\mid h(g(w,f))=1\}}$,

où

${\displaystyle f(q)={\begin{cases}1&{\text{si }}q\in F\\0&{\text{sinon}}\end{cases}}}$

Ici ${\displaystyle f}$ est la fonction caractéristique de l’ensemble ${\displaystyle F}$ des états terminaux, représentée comme vecteur booléen. Un mot ${\displaystyle w}$ est donc accepté si la fonction booléenne ${\displaystyle h}$ prend la valeur 1 sur le vecteur ${\displaystyle g(w,f)}$ qui lui est le vecteur booléens de tous les états ${\displaystyle q}$ pour lesquels le calcul de ${\displaystyle w}$ aboutit en un état final.

Les automates finis non déterministes sont un cas particulier automates alternants; tout langage rationnel est, par conséquent, accepté par un automate alternant. Réciproquement, tout automate alternant peut être transformé en automate fini déterministe. Les automates finis alternants acceptent donc précisément les langages réguliers. Toutefois, un automate alternant peut être beaucoup plus petit. On peut gagner une exponentielle en passant d'un automate non déterministe à un automate alternant, et une double exponentielle en passant d'un automate déterministe à un automate alternant. La borne exacte dépend de la définition exacte des automates alternants. Ainsi, quand on autorise les négations dans les formules booléennes, il existe un automate fini alternant avec ${\displaystyle n}$ états pour lequel le plus petit automate fini déterministe requiert ${\displaystyle 2^{2^{n}}}$ états. Quand on n’autorisent pas la négation, et alors la borne est ${\displaystyle 2^{2^{n}/{\sqrt {n}}}}$[2].

Les automates alternants, sur les mots infinis, se définissent de manière analogue, en prenant comme condition d'acceptation par exemple la condition des automates de Büchi. Les automates alternants reconnaissent les mêmes langages de mots infinis que les automates de Büchi non déterministes, mais l’alternance peut rendre les automates exponentiellement plus petits.

Il existe diverses variations dans la définition des automates finis alternants. Ils ne modifient pas la puissance d'expression, mais peuvent être plus ou moins faciles à définir et plus ou moins faciles à mettre en œuvre[3]. C’est surtout la souplesse de la structure combinatoire d’une automate alternant qui est appréciée[3] : elle simplifie considérablement la traduction de spécifications de propriétés en automates, traduction qui est à la base des algorithmes de model checking. Les automates sont utilisés pour la spécification et la vérification de programmes. Quand un programme est défini relativement à un ensemble P de propositions, chaque état dans une exécution du programme correspond à une partie de P, à savoir à l'ensemble des propositions qui sont vraie dans cet état. Une exécution du programme définit ainsi un mot fini ou infini sur l’alphabet des parties de P, et le programme lui-même donne un ensemble de mots qui peut être défini par un automate. De même, la spécification d’un programme qui décrit les calculs possibles peut être vu comme un langage de mots sur l’alphabet des parties de P, et donc être défini par un automate. Ainsi, les questions sur les programmes se ramènent à des questions sur des automates. Par exemple, les questions de la satisfiabilité de la spécification et de la correction d’un programme se réduisent à des questions comme le test du vide, ou au problème d’inclusion pour les langages formels. La traduction de spécifications vers les automates prend en charge les aspects logiques, et déplace les difficultés combinatoires vers des problèmes de théorie combinatoire[3].

Une variante des automates consiste à ne pas autoriser les négations. C'est l'option retenue dans certains travaux sur l'apprentissage de langages réguliers[4].

Une variante dans la définition[2] même des automates consiste à introduire un état initial ${\displaystyle q_{0}}$ à la place de la fonction d'évaluation ${\displaystyle h}$. La condition d'acceptation

${\displaystyle h(g(w,f))=1}$

est remplacée par la condition, plus contraignante en apparence, de

${\displaystyle g(q_{0},w,f)=1}$.

Une autre variante, plus marquée, consiste à définir les automates alternants comme suit[5] : L'ensemble ${\displaystyle Q}$ des états est divisé en deux parties, les états existentiels ${\displaystyle Q_{\exists }}$ et universels ${\displaystyle Q_{\forall }}$. L'idée sous-jacente est que les transitions sortant d'un état de ${\displaystyle Q_{\exists }}$ sont interprétées comme des transitions ou, et les transitions sortant d'un état de ${\displaystyle Q_{\forall }}$ comme des transitions et. Syntaxiquement, ceci est la seule différence entre automates alternants et automates non déterministes.

Soit ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,s,F,\delta )}$, avec ${\displaystyle Q=Q_{\exists }\cup Q_{\forall }}$ un automate fini non déterministe usuel. Un mot ${\displaystyle w}$ est accepté à partir d'un état ${\displaystyle q}$ si ${\displaystyle q}$ est un état final et ${\displaystyle w}$ est le mot vide, ou alors si ${\displaystyle w=av}$ pour une lettre ${\displaystyle a}$ et un mot ${\displaystyle v}$, et si soit :

• ${\displaystyle q\in Q_{\exists }}$, et ${\displaystyle v}$ est accepté par au moins un des états dans ${\displaystyle \delta (q,a)}$, ou
• ${\displaystyle q\in Q_{\forall }}$, et ${\displaystyle v}$ est accepté par tous les états dans ${\displaystyle \delta (q,a)}$.

Le langage accepté par un tel automate est l'ensemble des mots acceptés à partir de l’état initial.

La fonction de transition ${\displaystyle g\colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}}$ définie plus haut est remplacée par une fonction plus simple ${\displaystyle g\colon Q\times \Sigma \to \mathbb {B} (Q)}$ qui associe à un état ${\displaystyle q}$ et à une lettre ${\displaystyle a}$ une formule booléenne sur ${\displaystyle Q}$ : Pour un état ${\displaystyle q}$, une lettre ${\displaystyle a}$, et ${\displaystyle \delta (q,a)=\{q_{1},\ldots ,q_{k}\}}$, la fonction ${\displaystyle g}$ prend la valeur ${\displaystyle g(q,a)={\begin{cases}q_{1}\lor q_{2}\lor \cdots \lor q_{k}&{\text{si }}q\in Q_{\exists }\\q_{1}\land q_{2}\land \cdots \land q_{k}&{\text{si }}q\in Q_{\forall }\end{cases}}}$.

Article fondateur

• Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, n^o 1,‎ janvier 1981, p. 114-133 (DOI 10.1145/322234.322243).

Autres articles

• Orna Kupferman et Moshe Y. Vardi, « Weak alternating automata and tree automata emptiness », Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC '98),‎ 1998, p. 224-233 (DOI 10.1145/276698.276748, lire en ligne)
• Orna Kupferman et Moshe Y. Vardi, « Weak alternating automata are not that weak », ACM Transactions on Computational Logic, vol. 2, n^o 3,‎ 2001, p. 408-429 (DOI 10.1145/377978.377993, lire en ligne)
• Dana Angluin, Sarah Eisenstat et Dana Fisman, « Learning regular languages via alternating automata », Proceedings of the twenty-fourth international joint conference on artificial intelligence (IJCAI 2015),‎ 2015, p. 3308-3314 (lire en ligne)

Cours

• K. Narayan Kumar, « Alternating automata », Notes on Automata, Logic, Games and Algebra, Chennai Mathematical Institute, Chennai.
• Pascal Raiola, « Introduction to alternating finite automata », Automata Theory — Software Engineering, Informatik Universität Freiburg, 2013.

• Model checking
• Machine de Turing
• Automate sur les mots infinis

• Portail de l'informatique théorique