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)

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (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)