Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Alternating_finite_automaton> ?p ?o. }
Showing items 1 to 16 of
16
with 100 items per page.
- Alternating_finite_automaton abstract "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 tells that any AFA is equivalent to an non-deterministic finite automaton (NFA) by performing a similar kind of powerset construction as it is used for the transformation of an NFA to a deterministic finite automaton (DFA). This construction converts an AFA with k states to an NFA with up to states.An alternative model which is frequently used is the one where Boolean combinations are represented as clauses. For instance, one could assume the combinations to be in Disjunctive Normal Form so that would represent . The state tt (true) is represented by in this case and ff (false) by .This clause representation is usually more efficient.".
- Alternating_finite_automaton wikiPageID "779196".
- Alternating_finite_automaton wikiPageRevisionID "575677375".
- Alternating_finite_automaton hasPhotoCollection Alternating_finite_automaton.
- Alternating_finite_automaton subject Category:Automata_theory.
- Alternating_finite_automaton comment "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.".
- Alternating_finite_automaton label "Alternating finite automaton".
- Alternating_finite_automaton label "Alternerende eindige automaat".
- Alternating_finite_automaton label "Autômato finito alternado".
- Alternating_finite_automaton sameAs Alternerende_eindige_automaat.
- Alternating_finite_automaton sameAs Autômato_finito_alternado.
- Alternating_finite_automaton sameAs m.03bp2t.
- Alternating_finite_automaton sameAs Q3300791.
- Alternating_finite_automaton sameAs Q3300791.
- Alternating_finite_automaton wasDerivedFrom Alternating_finite_automaton?oldid=575677375.
- Alternating_finite_automaton isPrimaryTopicOf Alternating_finite_automaton.