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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:McNaughton's_theorem
rdfs:label
McNaughton's theorem Teorema de McNaughton
rdfs:comment
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. 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.
dcterms:subject
dbc:Automata_(computation)
dbo:wikiPageID
28167114
dbo:wikiPageRevisionID
1101156388
dbo:wikiPageWikiLink
dbr:DFA_minimization dbr:Automata_theory dbr:Omega-regular_language dbr:Regular_language dbr:Muller_automaton dbr:Büchi_automaton dbr:Ω-regular_language dbr:Semi-deterministic_Büchi_automaton dbr:Deterministic_finite_automaton dbr:W.l.o.g. dbc:Automata_(computation) dbr:Ω-language
owl:sameAs
dbpedia-fa:نظریه_مک‌ناتون freebase:m.0cmdmyp n15:4sDYH wikidata:Q6802493 dbpedia-pt:Teorema_de_McNaughton
dbp:wikiPageUsesTemplate
dbt:Refimprove
dbo:abstract
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. 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.
prov:wasDerivedFrom
wikipedia-en:McNaughton's_theorem?oldid=1101156388&ns=0
dbo:wikiPageLength
15071
foaf:isPrimaryTopicOf
wikipedia-en:McNaughton's_theorem