Automate fini alternant

En informatique théorique, et notamment en théorie des automates, un automate  fini alternant est une extension des  automates finis. Dans un automate fini non déterministe usuel, un mot  est accepté si, parmi les états atteints, il y a au moins un état final.  Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation. 

Le nom « alternant » est basé sur l'observation suivante : à condition d'autoriser les ε-transitions, deux types de conditions suffisent pour exprimer toutes les fonctions booléennes possibles sur les états : parmi les états atteints, au moins un est final ou bien tous sont finaux. Les choix varient donc entre un choix existentiel et un choix universel. 

Les automates finis alternants sont utilisés pour la reconnaissance de mots infinis, en théorie des jeux, en model checking et en logique. Ils trouvent des applications aussi en apprentissage automatique.

Description 
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  en passant d’un état au suivant selon la fonction de transition. L’automate accepte le mot  à partir d’un état  si l’état atteint après la lecture de  accepte le suffixe . Un automate non déterministe qui lit la lettre  dans un état  peut en revanche passer en plusieurs états, déterminés par la relation de transition. L’automate accepte   à partir de  si l’un des états  dans lesquels il peut passer après la lecture de  accepte le suffixe . Une notion duale est celle d’automate universel. Comme pour un automate non déterministe, la relation de transition donne, pour un état  et une lettre , un ensemble d’états; mais l’interprétation est ici que  est accepté depuis l’état  si tous les états  atteints après la lecture de  acceptent le suffixe .

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  , en lisant la lettre , va vers l'expression  , stipule que le mot  est accepté depuis  si son suffixe  est accepté depuis  ou à la fois depuis  et .

Définition formelle 

Un automate fini alternant  est composé des données suivantes : 
  un ensemble fini d'états ;
  un alphabet d'entrée ;
  un ensemble d'états terminaux ; 
 , une fonction d'acceptation ; 
  une fonction de transition.
L'état initial usuel dans les automates est remplacé par la fonction d'acceptation .
La fonction de transition  associe à un état , à une lettre  et à un vecteur d'états  indicé par  , une valeur booléenne. La fonction  est étendue au mots par les deux propriétés suivantes :
 , où  est la coordonnée d'indice  de .
 , où  est le vecteur .
Vue comme fonction opérant sur les vecteurs d'états, la fonction  est donc étendue par 

L'ensemble des mots acceptés par  est
 ,
où 

Ici  est la fonction caractéristique de l’ensemble  des états terminaux, représentée comme vecteur booléen. Un mot  est donc accepté si la fonction booléenne  prend la valeur 1 sur le vecteur  qui lui est le vecteur booléens de tous les états  pour lesquels le calcul de  aboutit en un état final.

Exemples

Un premier exemple 
On considère une automate à deux état et sur l'alphabet , l'ensemble des états terminaux est . La fonction de transition est donnée par

et la fonction d'acceptation est

Un exemple de calcul est alors

D'où

et le mot  est donc accepté.

Un deuxième exemple 
On considère un automate  sur l’alphabet  qui possède un seul état , état également final. La fonction de transition est donnée par :
 
 
et la fonction d'acceptation est . On voit que 

.

Le langage accepté par l'automate est donc : 
 .
Cet automate a un seul état, alors que plus petit automate non déterministe qui reconnaît son langage a 2 états, et le plus petit automate déterministe a 4 états.

Propriétés et usages 

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  états pour lequel le plus petit automate fini déterministe requiert  états. Quand on n’autorisent pas la négation, et alors la borne est . 

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.

Variations 
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. C’est surtout la souplesse de la structure combinatoire d’une automate alternant qui est appréciée : 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.

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.

Une variante dans la définition même des automates consiste à introduire un état initial  à la place de la fonction d'évaluation . La condition d'acceptation

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

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

Soit , avec  un automate fini non déterministe usuel. 
Un mot  est accepté à partir d'un état  si  est un état final et  est le mot vide, ou alors si  pour une lettre  et un mot , et si soit :
 , et  est accepté par au moins un des états dans , ou 
 , et  est accepté par tous les états dans .
Le langage accepté par un tel automate est l'ensemble des mots acceptés à partir de l’état initial.

La fonction de transition  définie plus haut est remplacée par une fonction plus simple 
qui associe à un état  et à une lettre  une formule booléenne sur  : 
Pour un état , une lettre , et , la fonction  prend la valeur
.

Notes et références

Bibliographie 
Article fondateur
 .
Autres articles
 
  
 
Cours
 .
 .

Articles liés 
 Model checking
 Machine de Turing
 Automate sur les mots infinis

Théorie des automates
Calculabilité
Méthode formelle
Automates finis et langages réguliers