Automate de büchi
- Automate de büchi
-
Automate de Büchi
Un automate de Büchi est un automate fini avec une condition d'acceptation particulière : une trace est acceptée si et seulement si elle passe un nombre infini de fois par au moins un état acceptant.
Les automates de Büchi déterministes et non déterministes ne sont pas équivalents. Par contre, tout automate de Büchi est équivalent à un automate de Rabin déterministe.
Les automates de Büchi non déterministes représentent exactement les propriétés de la logique monadique de second ordre à un successeur (S1S), dites aussi propriétés ω-régulières. La logique S1S est strictement plus expressive que la logique temporelle linéaire.
Références
- Wolfgang Thomas, Automata on infinite objects, dans Handbook of Theoretical Computer Science : Formal Models and Semantics, tome B (Jan Van Leeuwen, éd.), MIT Press, ISBN 0-262-72015-9
Catégories : Calculabilité | Langage formel
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Automate de büchi de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Automate de Büchi — non déterministe reconnaissant les mots infinis contenant un nombre fini le a En informatique théorique, un automate de Büchi est un automate fini acceptant des mots infinis, avec une condition d acceptation particulière : une trace (ou… … Wikipédia en Français
Automate De Büchi — Un automate de Büchi est un automate fini avec une condition d acceptation particulière : une trace est acceptée si et seulement si elle passe un nombre infini de fois par au moins un état acceptant. Les automates de Büchi déterministes et… … Wikipédia en Français
Automate de Buchi — Automate de Büchi Un automate de Büchi est un automate fini avec une condition d acceptation particulière : une trace est acceptée si et seulement si elle passe un nombre infini de fois par au moins un état acceptant. Les automates de Büchi… … Wikipédia en Français
Automate Fini — Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate déterministe à états fini — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini non déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Automate fini non déterministe généralisé — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine … Wikipédia en Français
Buchi — Büchi Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Büchi est un patronyme : Alfred Büchi, ingénieur suisse, en 1905, il a dépose un brevet de turbocompresseur. Albert Büchi, cycliste suisse,… … Wikipédia en Français
Automate sur les mots infinis — En informatique théorique, et spécialement en théorie des automates un automate sur les mots infinis ou ω automate est un automate fini, déterministe ou non, qui accepte des mots infins. Comme un tel automate ne s arrête pas, les conditions d… … Wikipédia en Français
