In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite state automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton which visits (at least) one of the final states infinitely often. Büchi automata recognize the omega-regular languages, the infinite word version of regular languages. It is named after the Swiss mathematician Julius Richard Büchi who invented this kind of automaton in 1962.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- Der Büchi-Automat (nach dem Schweizer Mathematiker Julius Richard Büchi) ist eine spezielle Form des ω-Automaten. Dieser Automatentyp kann benutzt werden, um sowohl Sprachen über unendliche Wörter als auch über unendliche Bäume zu erkennen.
- Automat Büchiego to rozszerzenie automatu skończonego na słowa nieskończone. Automat Büchiego składa się z: alfabetu zbioru stanów z wyróżnionym stanem startowym oraz podzbiorem stanów akceptujących funkcji przejścia, która pobiera aktualny stan oraz literę alfabetu i zwraca nowy stan (deterministyczne automaty Büchiego), lub relacji przejścia, która może zwracać wiele stanów (niedeterministyczne automaty Büchiego) Słowo (nieskończone) jest akceptowane przez automat Büchiego, jeśli stan akceptujący wystąpi w tym słowie nieskończenie wiele razy. W przeciwieństwie do zwykłych automatów skończonych, gdzie automaty deterministyczne i niedeterministyczne miały taką samą moc, niedeterministyczne automaty Büchiego są silniejsze od deterministycznych. Niedeterministyczne automaty Büchiego są zamknięte ze względu na dopełnienie, przecięcie i alternatywę. Dopełnienie automatu deterministycznego może być automatem niedeterministycznym.
- In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite state automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton which visits (at least) one of the final states infinitely often. Büchi automata recognize the omega-regular languages, the infinite word version of regular languages. It is named after the Swiss mathematician Julius Richard Büchi who invented this kind of automaton in 1962. Büchi automata are often used in Model checking as an automata-theoretic version of a formula in linear temporal logic.
- 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 calcul ou chemin infini) est réussie si et seulement si elle passe un nombre infini de fois par au moins un état acceptant. Un mot infini est accepté s'il est l'étiquette d'un calcul réussi. Ce type d'automate a été défini par le mathématicien Julius Richard Büchi. Les automates de Büchi déterministes et non déterministes ne sont pas équivalents. Par exemple, il n'existe pas d'automate de Büchi déterministe qui reconnaît les mots infinis sur deux lettres et qui ne contiennent qu'un nombre fini de lettres, c'est-à-dire l'ensemble, alors que cet ensemble est reconnu par un automate de Büchi non déterministe à deux états. Les ensembles de mots infinis reconnus par les automates de Büchi sont les ensembles de la forme où les et sont des langages rationnels pour tout . Ceci signifie que les automates de Büchi sont équivalents aux automates de Muller, aux automates de Rabin, automates de Streett ou automates de parité. 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.
|
| dbpedia-owl:wikiPageExternalLink
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Der Büchi-Automat (nach dem Schweizer Mathematiker Julius Richard Büchi) ist eine spezielle Form des ω-Automaten. Dieser Automatentyp kann benutzt werden, um sowohl Sprachen über unendliche Wörter als auch über unendliche Bäume zu erkennen.
- Automat Büchiego to rozszerzenie automatu skończonego na słowa nieskończone.
- In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite state automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton which visits (at least) one of the final states infinitely often. Büchi automata recognize the omega-regular languages, the infinite word version of regular languages. It is named after the Swiss mathematician Julius Richard Büchi who invented this kind of automaton in 1962.
- 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 calcul ou chemin infini) est réussie si et seulement si elle passe un nombre infini de fois par au moins un état acceptant. Un mot infini est accepté s'il est l'étiquette d'un calcul réussi. Ce type d'automate a été défini par le mathématicien Julius Richard Büchi.
|
| rdfs:label
|
- Büchi-Automat
- Büchi automaton
- Automate de Büchi
- Automat Büchiego
|
| owl:sameAs
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
