Théories des automates, informatique théorique, mécanisme mathématique, Concepts de la théorie des automates (Alphabet, Mots ou chaînes, Langage formel, étude des machines abstraites.
Calculabilité, par le modèle des machines de Turing, Automates finis, et leurs variantes, qui sont utilisés dans l'analyse des langues naturelles, La théorie de la complexité des algorithmes, visant à classifier les algorithmes en fonction des ressources temporelles La vérification de modèle qui sert à établir la conformité de programmes à leurs spécifications. Voir par exemple Rocq.
Caractéristiques des automates
- Automate prend en entrée des données discrètes
- Automate possède un nombre fini de configurations internes,
- Automate peut disposer, par ailleurs, d'une mémoire auxiliaire externe,
- Automate possède un certain nombre de configurations d'acceptation.
Typologies des automates
- Automates finis,
- Automates sur les mots infinis,
- Automates temporisés,
- Automates probabilistes,
- Automates quantiques,
- Automates pondérés,
- Automates bidirectionnels,
- Automate alternant,
- Automate séquentiel,
- Automate de Parikh,
- Modèles de Markov caché,
- Systèmes de transitions, structure de Kripke,
- Automates à pile,
- Automates à file,
- Automates à pile emboîtée, à pile visible, à pile de piles,
- Automates d'arbres,
- Automates cheminant dans un arbre, à jetons,
- Systèmes de réécriture,
- Réseaux de Petri,
- Automates linéairement bornés,
- Machines de Turing,
