In automata theory, McNaughton's theorem refers to a theorem that asserts that the set of ω-regular languages is identical to the set of languages recognizable by deterministic Muller automata.This theorem is proven by supplying an algorithm to construct a deterministic Muller automaton for any ω-regular language and vice versa.
Attributes | Values |
---|
rdfs:label
| - McNaughton's theorem (en)
- Teorema de McNaughton (pt)
|
rdfs:comment
| - In automata theory, McNaughton's theorem refers to a theorem that asserts that the set of ω-regular languages is identical to the set of languages recognizable by deterministic Muller automata.This theorem is proven by supplying an algorithm to construct a deterministic Muller automaton for any ω-regular language and vice versa. (en)
- Em teoria dos autômatos, o teorema de McNaughton refere-se a um teorema que afirma que o conjunto de linguagens ω-regulares é idêntico ao conjunto de linguagens reconhecíveis por autômatos de Muller determinísticos.Este teorema é provado através do fornecimento de um algoritmo para construir um autômato de Muller determinístico para qualquer linguagem ω-regular e vice-versa. (pt)
|
dct:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - In automata theory, McNaughton's theorem refers to a theorem that asserts that the set of ω-regular languages is identical to the set of languages recognizable by deterministic Muller automata.This theorem is proven by supplying an algorithm to construct a deterministic Muller automaton for any ω-regular language and vice versa. This theorem has many important consequences.Since Büchi automata and ω-regular languages are equally expressive, the theorem implies that Büchi automata and deterministic Muller automata are equally expressive.Since complementation of deterministic Muller automata is trivial, the theorem implies that Büchi automata/ω-regular languages are closed under complementation. (en)
- Em teoria dos autômatos, o teorema de McNaughton refere-se a um teorema que afirma que o conjunto de linguagens ω-regulares é idêntico ao conjunto de linguagens reconhecíveis por autômatos de Muller determinísticos.Este teorema é provado através do fornecimento de um algoritmo para construir um autômato de Muller determinístico para qualquer linguagem ω-regular e vice-versa. Este teorema tem muitas consequências importantes. Tendo em vista que autômatos de Büchi e linguagens ω-regulares, são expressivos igualmente, o teorema implica que autômatos de Büchi e autômatos de Muller determinísticos também são expressivos igualmente.Visto que a complementação de autômatos de Muller determinísticos é trivial, o teorema implica que autômatos de Büchi/linguagens ω-regulares são fechados sob complementação. (pt)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is foaf:primaryTopic
of | |