Structure oméga-automatique

Une structure oméga-automatique est une structure représentée par des automates finis acceptant des mots infinis.

Ces structures constituent une extension des structures automatiques pour des ensembles ayant la puissance du continu. Elles possèdent les mêmes propriétés de décidabilité au premier ordre que ces dernières^[1].

Notes et références

↑ (en) Achim Blumensath et Erich Grädel, « Automatic Structures », Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society, série LICS '00,‎ 1^er janvier 2000, p. 51 (lire en ligne)

v · m Automates finis et langages réguliers
Articles généraux	Théorie des automates Automate fini Machine abstraite
Automates finis	Automate fini déterministe Automate fini inambigu Automate fini non déterministe Construction par sous-ensembles Automate sur les mots infinis
Automates finis particuliers	Automate alternant Automate bidirectionnel Automate pondéré Automate probabiliste Automate quantique Automate temporisé Automate de Büchi Automate de Muller Modèle de Markov caché Système de transition d'états Structure de Kripke Machine à états abstraits Machine de Mealy Machine de Moore Transducteur fini Automate séquentiel
Langages réguliers	Langage rationnel Langage sans étoile Langage local Langage congruentiel Langage stochastique Lemme de l'étoile Lemme d'Arden ω-langage rationnel
Des automates aux langages	Expression régulière Algorithme de Conway Algorithme de McNaughton et Yamada Méthode de Brzozowski et McCluskey
Des langages aux automates	Dérivée de Brzozowski Algorithme de Thompson Construction de Glushkov Complexité en états
Minimisation	Théorème de Myhill-Nerode Équivalence de Nerode Minimisation d'un automate fini déterministe Algorithme de Moore Algorithme de Brzozowski Algorithme de Hopcroft
Équivalences	Théorème de Kleene Étoile de Kleene Monoïde syntaxique Théorème des variétés d'Eilenberg

Portail de l'informatique théorique