In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machine should move to from its current state when it reads the next input character. Some states are accepting states and one state is the start state. The machine accepts an input if and only if it will pass through an accepting state infinitely many times as it reads the input.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Büchiho automat (cs)
- Büchi-Automat (de)
- Büchi automaton (en)
- Automate de Büchi (fr)
- Automa di Büchi (it)
- Automat Büchiego (pl)
- Autômato de Büchi (pt)
|
rdfs:comment
| - Büchiho automat je v teorii automatů ω-automat, který rozšiřuje koncept konečného automatu pro nekonečné vstupy (slova nekonečné délky). Büchiho automat akceptuje slovo, pokud existuje běh automatu, který navštíví alespoň jeden koncový stav nekonečněkrát. Automat je pojmenován po švýcarském matematikovi , který ho vynalezl v roce 1962. (cs)
- 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 unendlichen Wörtern als auch über unendlichen Bäumen zu erkennen. (de)
- En informatique théorique, un automate de Büchi est un ω-automate ou automate fini opérant sur 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 est utilisé en vérification de modèles. Ce type d'automate a été défini par le mathématicien Julius Richard Büchi. (fr)
- In informatica teorica, un automa di Büchi è un ω-automa o automa finito che opera su parole di lunghezza infinita, con una particolare condizione di accettazione: una traccia ha successo se e solo se passa un numero infinito di volte per almeno uno stato accettante. Questo tipo di automa viene comunemente utilizzato per il model checking. Questo tipo di automa è stato definito dal matematico Julius Richard Büchi. (it)
- In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machine should move to from its current state when it reads the next input character. Some states are accepting states and one state is the start state. The machine accepts an input if and only if it will pass through an accepting state infinitely many times as it reads the input. (en)
- Automat Büchiego (ang. Büchi automaton) 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. (pl)
- Em ciência da computação e teoria dos autômatos, um Autômato de Büchi é um tipo de autômato ω, que estende um para entradas infinitas. Ele aceita como entrada uma sequência infinita sse existe uma execução do autômato que visita (pelo menos) um dos estados finais infinitas vezes. Autômato de Büchi reconhece a linguagem Omega-regular, a versão da palavra infinita das linguagens regulares. Foi assim denominada por causa do matemático suíço Julius Richard Büchi que inventou esse tipo de autômato em 1962. (pt)
|
foaf:depiction
| |
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
thumbnail
| |
has abstract
| - Büchiho automat je v teorii automatů ω-automat, který rozšiřuje koncept konečného automatu pro nekonečné vstupy (slova nekonečné délky). Büchiho automat akceptuje slovo, pokud existuje běh automatu, který navštíví alespoň jeden koncový stav nekonečněkrát. Automat je pojmenován po švýcarském matematikovi , který ho vynalezl v roce 1962. (cs)
- 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 unendlichen Wörtern als auch über unendlichen Bäumen zu erkennen. (de)
- In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machine should move to from its current state when it reads the next input character. Some states are accepting states and one state is the start state. The machine accepts an input if and only if it will pass through an accepting state infinitely many times as it reads the input. A non-deterministic Büchi automaton, later referred to just as a Büchi automaton, has a transition function which may have multiple outputs, leading to many possible paths for the same input; it accepts an infinite input if and only if some possible path is accepting. Deterministic and non-deterministic Büchi automata generalize deterministic finite automata and nondeterministic finite automata to infinite inputs. Each are types of ω-automata. Büchi automata recognize the ω-regular languages, the infinite word version of regular languages. They are named after the Swiss mathematician Julius Richard Büchi, who invented them in 1962. Büchi automata are often used in model checking as an automata-theoretic version of a formula in linear temporal logic. (en)
- En informatique théorique, un automate de Büchi est un ω-automate ou automate fini opérant sur 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 est utilisé en vérification de modèles. Ce type d'automate a été défini par le mathématicien Julius Richard Büchi. (fr)
- In informatica teorica, un automa di Büchi è un ω-automa o automa finito che opera su parole di lunghezza infinita, con una particolare condizione di accettazione: una traccia ha successo se e solo se passa un numero infinito di volte per almeno uno stato accettante. Questo tipo di automa viene comunemente utilizzato per il model checking. Questo tipo di automa è stato definito dal matematico Julius Richard Büchi. (it)
|