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
Ce document provient de « Automate de B%C3%BCchi ».

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”