This HTML5 document contains 88 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

dbr:Ω-automaton

rdf:type

dbr:Variation dbo:Food

rdfs:label

Ω-automaton Automate sur les mots infinis Ω-automat Autômato ω Omega automa Ω-Automat

rdfs:comment

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. 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. 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. Ω-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. 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. 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.

owl:sameAs

dbpedia-fr:Automate_sur_les_mots_infinis wd:Q291256 n16:09v63p6 dbpedia-pt:Autômato_ω dbr:Ω-automaton dbpedia-de:Ω-Automat dbpedia-cs:Ω-automat dbpedia-it:Omega_automa dbpedia-fa:ماشین_امگا n27:2hLfA

foaf:topic

dbr:Nondeterministic_finite_automaton wikipedia-en:Ω-automaton dbr:Parity_automaton dbr:Stream_automaton dbr:Co-Büchi_automaton dbr:Rabin_automaton dbr:Omega_automata dbr:Omega_automaton dbr:Streett_automaton dbr:Muller_automaton dbr:Streett_automata n9: dbr:Regular_language dbr:Generalized_Büchi_automaton dbr:Infinite-tree_automaton dbr:Powerset_construction dbr:Determinacy dbr:Ω-automata n29:this dbr:Probabilistic_automaton dbr:Büchi_automaton

foaf:depiction

n30:svg

dct:subject

dbc:Finite_automata

dbo:wikiPageID

25654012

dbo:wikiPageRevisionID

1121888768

dbo:wikiPageWikiLink

dbr:Treewidth dbr:MIT_Press n9: dbr:Büchi_automaton n10:s_construction dbr:Finite_set n11:svg dbr:Infinite-tree_automaton dbr:Lecture_Notes_in_Computer_Science dbr:Automata_theory dbr:Power_set dbr:Ordinal_number dbr:Monadic_second-order_logic dbr:Omega-regular_language dbr:Operating_systems dbc:Finite_automata dbr:Theoretical_computer_science dbr:Ω-automaton dbr:Elsevier dbr:Ω-language dbr:Muller_automaton dbr:Control_systems dbr:Finite_automaton

dbo:wikiPageExternalLink

n13:6

foaf:isPrimaryTopicOf

wikipedia-en:Ω-automaton

prov:wasDerivedFrom

n15:0

n28:hypernym

dbr:Variation

dbo:abstract

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 ω. 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. 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é. 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. 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. Ω-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.

dbo:thumbnail

n23:300

dbo:wikiPageLength

14803

dbp:wikiPageUsesTemplate

dbt:Vanchor dbt:Cite_book dbt:Citation dbt:Reflist