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.
Abstract from DBpedia / Wikipedia · CC BY-SA
Discovered by embedding cosine similarity (sentence-transformers MiniLM, 384-dim).