| comment
| - Ein ω-Automat (Omega-Automat) ist ein mathematisches Modell, das eine Erweiterung des endlichen Automaten auf die Eingabe unendlicher Wörter darstellt. Endlich heißt der Automat deshalb, weil die Anzahl seiner inneren Zustände endlich ist. Ebenso ist das Alphabet, über dem dieser Automat arbeitet, endlich. Der griechische Buchstabe ω (omega) steht hier für die kleinste unendliche Ordinalzahl. Motiviert wird die Betrachtung solcher Automaten durch viele Systeme (zum Beispiel Betriebssysteme), die per definitionem eigentlich nicht terminieren sollen, sondern unendlich lange betrieben werden.
- En informatique théorique, et spécialement en théorie des automates, un automate sur les mots infinis ou ω-automate est un automate fini qui accepte des mots infinis. Un tel automate lit un mot infini, ainsi, l'exécution ne s'arrête pas ; les conditions d'acceptation portent sur l'exécution elle-même là où elles ne traitent que de l'état d'arrivée (et de la possibilité de lire le mot) dans le cas des automates sur les mots finis.
- Na teoria de autômatos, um ramo da teoria da computação, um autômato ω é uma variação do autômato finito que roda sobre cadeias infinitas como entrada, ao invés de finitas. Uma vez que um ω-autômato não para, eles têm uma variedade de condições de aceitação, em vez de simplesmente um conjunto de estados de aceitação.
- Un ω-automa o automa su parole infinite è, in informatica teorica e specialmente nella teoria degli automi, è un automa a stati finiti che accetta parole di lunghezza infinita. Gli automi su parole infinite vengono utilizzati per modellare calcoli che non si completano, come il comportamento di un sistema operativo o di un sistema di controllo. Per tali sistemi, è possibile specificare proprietà come "ogni richiesta sarà seguita da una risposta" o la sua negazione "c'è una richiesta che non è seguita da una risposta" nell'ambito della verificazione di modelli (o model checking). Tali proprietà possono essere formulate per infinite parole e possono essere verificate da automi finiti.
- Ω-automat je v teorii automatů varianta konečného automatu, který na vstupu zpracovává slovo nekonečné délky. Protože výpočet ω-automatů běží nekonečně dlouho, liší se jednotlivé automaty akceptujícími podmínkami namísto pouhého definování koncových stavů jako u automatů zpracovávajících slova konečné délky.
- In automata theory, a branch of theoretical computer science, an ω-automaton (or stream automaton) is a variation of finite automata that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states.
|
| dbo:abstract
| - Ein ω-Automat (Omega-Automat) ist ein mathematisches Modell, das eine Erweiterung des endlichen Automaten auf die Eingabe unendlicher Wörter darstellt. Endlich heißt der Automat deshalb, weil die Anzahl seiner inneren Zustände endlich ist. Ebenso ist das Alphabet, über dem dieser Automat arbeitet, endlich. Der griechische Buchstabe ω (omega) steht hier für die kleinste unendliche Ordinalzahl. Motiviert wird die Betrachtung solcher Automaten durch viele Systeme (zum Beispiel Betriebssysteme), die per definitionem eigentlich nicht terminieren sollen, sondern unendlich lange betrieben werden.
- En informatique théorique, et spécialement en théorie des automates, un automate sur les mots infinis ou ω-automate est un automate fini qui accepte des mots infinis. Un tel automate lit un mot infini, ainsi, l'exécution ne s'arrête pas ; les conditions d'acceptation portent sur l'exécution elle-même là où elles ne traitent que de l'état d'arrivée (et de la possibilité de lire le mot) dans le cas des automates sur les mots finis. Les automates sur les mots infinis servent à modéliser des calculs qui ne terminent pas, comme le comportement d'un système d'exploitation, ou d'un système de contrôle. Pour de tels systèmes, on peut spécifier des propriétés comme « chaque requête sera suivie d'une réponse » ou sa négation « il existe une requête qui n'est pas suivie d'une réponse ». De telle propriétés peuvent être formulées pour des mots infinis et peuvent être vérifiées par des automates finis. Plusieurs classes d'automates sur les mots infinis ont été introduites : les automates de Büchi, automates de Rabin, automates de Streett, automates de parité, automates de Muller et, pour chaque classe, les automates déterministes ou non. Ces classes diffèrent seulement par leur condition d'acceptation. Toutes ces classes, à l'exception notable des automates de Büchi déterministes, reconnaissent la même famille d'ensembles de mots infinis, appelés ensembles rationnels de mots infinis ou ω-langages rationnels. Ces automates, même s'ils acceptent les mêmes langages, peuvent varier en taille pour un langage donné.
- In automata theory, a branch of theoretical computer science, an ω-automaton (or stream automaton) is a variation of finite automata that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states. ω-automata are useful for specifying behavior of systems that are not expected to terminate, such as hardware, operating systems and control systems. For such systems, one may want to specify a property such as "for every request, an acknowledge eventually follows", or its negation "there is a request that is not followed by an acknowledge". The former is a property of infinite words: one cannot say of a finite sequence that it satisfies this property. Classes of ω-automata include the Büchi automata, Rabin automata, Streett automata, parity automata and Muller automata, each deterministic or non-deterministic. These classes of ω-automata differ only in terms of acceptance condition. They all recognize precisely the regular ω-languages except for the deterministic Büchi automata, which is strictly weaker than all the others. Although all these types of automata recognize the same set of ω-languages, they nonetheless differ in succinctness of representation for a given ω-language.
- Ω-automat je v teorii automatů varianta konečného automatu, který na vstupu zpracovává slovo nekonečné délky. Protože výpočet ω-automatů běží nekonečně dlouho, liší se jednotlivé automaty akceptujícími podmínkami namísto pouhého definování koncových stavů jako u automatů zpracovávajících slova konečné délky.
- Un ω-automa o automa su parole infinite è, in informatica teorica e specialmente nella teoria degli automi, è un automa a stati finiti che accetta parole di lunghezza infinita. Gli automi su parole infinite vengono utilizzati per modellare calcoli che non si completano, come il comportamento di un sistema operativo o di un sistema di controllo. Per tali sistemi, è possibile specificare proprietà come "ogni richiesta sarà seguita da una risposta" o la sua negazione "c'è una richiesta che non è seguita da una risposta" nell'ambito della verificazione di modelli (o model checking). Tali proprietà possono essere formulate per infinite parole e possono essere verificate da automi finiti. Sono state introdotte diverse classi di automi su parole di lunghezza infinita: gli automi di Büchi, , , automi a parità, e, per ogni classe, versioni deterministiche o non deterministiche. Queste classi differiscono solo nella loro condizione di accettazione. Tutte queste classi, con la notevole eccezione degli automi di Büchi deterministici, riconoscono la stessa famiglia di insiemi di parole infinite, chiamati insiemi regolari di parole infinite o linguaggi ω-regolari. Questi automi, anche se accettano gli stessi linguaggi, possono variare di dimensioni su uno specifico linguaggio.
- Na teoria de autômatos, um ramo da teoria da computação, um autômato ω é uma variação do autômato finito que roda sobre cadeias infinitas como entrada, ao invés de finitas. Uma vez que um ω-autômato não para, eles têm uma variedade de condições de aceitação, em vez de simplesmente um conjunto de estados de aceitação. ω-autômatos são úteis para a especificação de comportamento de sistemas que não são esperados para terminar, como hardware, sistemas operacionais e Para tais sistemas, você pode querer especificar uma propriedade, como "para cada pedido, uma confirmação, eventualmente, segue", ou sua negação "existe um pedido que não é seguido por uma confirmação". O último é uma propriedade das palavras infinitas: nada se pode dizer de uma sequência finita que satisfaz esta propriedade. Classes de ω-autômatos incluem o , 'Rabin de autômatos', 'autômatos de Streett, 'autômatos de paridade e , determinístico ou não determinístico. Essas classes de ω-autômatos diferem apenas em termos de Todos eles reconhecem precisamente a , excepto pelos autômatos do Büchi determinísticos, que são estritamente mais fracos do que todos os outros. Embora todos estes tipos de autômatos reconhecem o mesmo conjunto de , eles ainda diferem em concisão de representação para uma dada linguagem ω.
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
