This HTML5 document contains 71 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/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n20https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-hrhttp://hr.dbpedia.org/resource/
dbpedia-srhttp://sr.dbpedia.org/resource/
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#
n7http://bs.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-nlhttp://nl.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Nondeterministic_finite_automaton
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Induction_of_regular_languages
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Language_equation
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Alternating_Finite_Automaton
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
dbo:wikiPageRedirects
dbr:Alternating_finite_automaton
Subject Item
dbr:Alternating_finite_automaton
rdfs:label
Alternating finite automaton Automate fini alternant Alternerende eindige automaat Autômato finito alternado
rdfs:comment
In de theoretische informatica is een alternerende eindige automaat een variant op een eindige automaat. Een toestand van een eindige automaat accepteert een woord , waarbij een symbool van het alfabet is en de rest van het woord, wanneer minstens een van zijn -opvolgertoestanden de accepteert. Een alternerende eindige automaat past echter een willekeurige booleaanse functie op de acceptatiewaardes van zijn opvolgertoestanden toe. Na teoria dos autômatos, um autômato finito alternado (AFA) é um autômato finito não-determinístico cujas transições são dividas em transições existenciais e universais. Por exemplo, consideremos A como um autômato alternado. * Para uma transição existencial , A escolhe não-deterministicamente mudar o estado para ou , lendo a. Comportando-se, assim, como um autômato finito não-determinístico regular. * Para uma transição universal , A move para e , lendo a, simulando o comportamento de uma máquina paralela. In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton. * For an existential transition , A nondeterministically chooses to switch the state to either or , reading a. Thus, behaving like a regular nondeterministic finite automaton. * For a universal transition , A moves to and , reading a, simulating the behavior of a parallel machine. En informatique théorique, et notamment en théorie des automates, un automate fini alternant est une extension des automates finis. Dans un automate fini non déterministe usuel, un mot est accepté si, parmi les états atteints, il y a au moins un état final. Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation. Les automates finis alternants sont utilisés pour la reconnaissance de mots infinis, en théorie des jeux, en model checking et en logique. Ils trouvent des applications aussi en apprentissage automatique.
dcterms:subject
dbc:Finite_automata
dbo:wikiPageID
779196
dbo:wikiPageRevisionID
1115928338
dbo:wikiPageWikiLink
dbr:Ashok_K._Chandra dbr:Cambridge_University_Press dbc:Finite_automata dbr:Word_(formal_languages) dbr:Alternating_tree_automaton dbr:Unary_language dbr:P-complete dbr:Disjunctive_normal_form dbr:Dexter_Kozen dbr:Existential_quantification dbr:Larry_Stockmeyer dbr:PSPACE-complete dbr:Deterministic_finite_automaton dbr:Tree_automaton dbr:N-tuple dbr:Automata_theory dbr:Nondeterministic_finite_automaton dbr:Regular_language dbr:Automaton dbr:Universal_quantification
owl:sameAs
n7:Alternirajući_konačni_automat dbpedia-pt:Autômato_finito_alternado dbpedia-nl:Alternerende_eindige_automaat dbpedia-hr:Alternirajući_konačni_automat freebase:m.03bp2t dbpedia-sr:Alternirajući_konačni_automat dbpedia-fr:Automate_fini_alternant n20:33L36 dbpedia-fa:ماشین_متناهی_متغیر yago-res:Alternating_finite_automaton wikidata:Q3300791
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:R dbt:Cite_book dbt:Main_article
dbo:abstract
En informatique théorique, et notamment en théorie des automates, un automate fini alternant est une extension des automates finis. Dans un automate fini non déterministe usuel, un mot est accepté si, parmi les états atteints, il y a au moins un état final. Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation. Le nom « alternant » est basé sur l'observation suivante : à condition d'autoriser les ε-transitions, deux types de conditions suffisent pour exprimer toutes les fonctions booléennes possibles sur les états : parmi les états atteints, au moins un est final ou bien tous sont finaux. Les choix varient donc entre un choix existentiel et un choix universel. Les automates finis alternants sont utilisés pour la reconnaissance de mots infinis, en théorie des jeux, en model checking et en logique. Ils trouvent des applications aussi en apprentissage automatique. In de theoretische informatica is een alternerende eindige automaat een variant op een eindige automaat. Een toestand van een eindige automaat accepteert een woord , waarbij een symbool van het alfabet is en de rest van het woord, wanneer minstens een van zijn -opvolgertoestanden de accepteert. Een alternerende eindige automaat past echter een willekeurige booleaanse functie op de acceptatiewaardes van zijn opvolgertoestanden toe. De naam baseert zich op het volgende: Als we lege overgangen toestaan (wat in het geval van eindige automaten niet gebruikelijk is), hebben we slechts twee soorten toestanden nodig om alle mogelijke booleaanse functies te kunnen uitdrukken: toestanden die accepteren als alle opvolgertoestanden accepteren, en toestanden die accepteren als minstens één opvolgertoestand accepteert. De automaat alterneert dan als het ware tussen "alle"- en "één"-toestanden. In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton. * For an existential transition , A nondeterministically chooses to switch the state to either or , reading a. Thus, behaving like a regular nondeterministic finite automaton. * For a universal transition , A moves to and , reading a, simulating the behavior of a parallel machine. Note that due to the universal quantification a run is represented by a run tree. A accepts a word w, if there exists a run tree on w such that every path ends in an accepting state. A basic theorem states that any AFA is equivalent to a deterministic finite automaton (DFA), hence AFAs accept exactly the regular languages. An alternative model which is frequently used is the one where Boolean combinations are in disjunctive normal form so that, e.g., would represent . The state tt (true) is represented by in this case and ff (false) by . This representation is usually more efficient. Alternating finite automata can be extended to accept trees in the same way as tree automata, yielding alternating tree automata. Na teoria dos autômatos, um autômato finito alternado (AFA) é um autômato finito não-determinístico cujas transições são dividas em transições existenciais e universais. Por exemplo, consideremos A como um autômato alternado. * Para uma transição existencial , A escolhe não-deterministicamente mudar o estado para ou , lendo a. Comportando-se, assim, como um autômato finito não-determinístico regular. * Para uma transição universal , A move para e , lendo a, simulando o comportamento de uma máquina paralela. Por causa do quantificador universal uma execução é representada por uma árvore de execuções. A aceita uma palavra w, se existe uma árvore de execução sobre w na qual todo caminho termina em um estado de aceitação. Um teorema básico diz que qualquer AFA é equivalente a um autômato finito não determinístico (AFN), executando um tipo similar de construção tão poderosa como a que é usada na transformação de um AFN para um autômato finito determinístico (AFD). Essa construção converte um AFA com k estados para um AFN que possui até estados. Um modelo alternativo que é frequentemente usado é aquele em que combinações de booleanas são representados como cláusulas.Por exemplo, pode-se assumir as combinações para estar na Forma Normal Disjuntiva então poderia representar . O estado tt (true) é representado por nesse caso e ff (false) por . Essa representação de cláusulas é normalmente mais eficiente.
prov:wasDerivedFrom
wikipedia-en:Alternating_finite_automaton?oldid=1115928338&ns=0
dbo:wikiPageLength
5284
foaf:isPrimaryTopicOf
wikipedia-en:Alternating_finite_automaton
Subject Item
dbr:Alternating_timed_automaton
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Alternating_tree_automata
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Regular_language
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:AFA
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
dbo:wikiPageDisambiguates
dbr:Alternating_finite_automaton
Subject Item
dbr:State_complexity
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Finite-state_machine
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Two-way_finite_automaton
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
Subject Item
dbr:Alternating_automata
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
dbo:wikiPageRedirects
dbr:Alternating_finite_automaton
Subject Item
dbr:Alternating_automaton
dbo:wikiPageWikiLink
dbr:Alternating_finite_automaton
dbo:wikiPageRedirects
dbr:Alternating_finite_automaton
Subject Item
wikipedia-en:Alternating_finite_automaton
foaf:primaryTopic
dbr:Alternating_finite_automaton