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. 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.