Self-verifying finite automaton (original) (raw)
In automata theory, a self-verifying finite automaton (SVFA)is a special kind of a nondeterministic finite automaton (NFA)with a symmetric kind of nondeterminismintroduced by Hromkovič and Schnitger.Generally, in self-verifying nondeterminism,each computation path is concluded with any of the three possible answers:yes, no, and I do not know.For each input string, no two pathsmay give contradictory answers,namely both answers yes and no on the same input are not possible.At least one path must give answer yes or no,and if it is yes then the string is considered accepted.SVFA accept the same class of languages as deterministic finite automata (DFA)and NFA but have different state complexity.
| Property | Value |
|---|---|
| dbo:abstract | In automata theory, a self-verifying finite automaton (SVFA)is a special kind of a nondeterministic finite automaton (NFA)with a symmetric kind of nondeterminismintroduced by Hromkovič and Schnitger.Generally, in self-verifying nondeterminism,each computation path is concluded with any of the three possible answers:yes, no, and I do not know.For each input string, no two pathsmay give contradictory answers,namely both answers yes and no on the same input are not possible.At least one path must give answer yes or no,and if it is yes then the string is considered accepted.SVFA accept the same class of languages as deterministic finite automata (DFA)and NFA but have different state complexity. (en) |
| dbo:wikiPageID | 53554923 (xsd:integer) |
| dbo:wikiPageLength | 3791 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032064700 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Nondeterministic_finite_automaton dbr:Deterministic_finite_automata dbr:Giovanni_Pighizzini dbr:Juraj_Hromkovič dbc:Finite_automata dbr:State_complexity dbr:Automata_theory dbr:N-tuple |
| dbp:wikiPageUsesTemplate | dbt:Reflist |
| dct:subject | dbc:Finite_automata |
| rdfs:comment | In automata theory, a self-verifying finite automaton (SVFA)is a special kind of a nondeterministic finite automaton (NFA)with a symmetric kind of nondeterminismintroduced by Hromkovič and Schnitger.Generally, in self-verifying nondeterminism,each computation path is concluded with any of the three possible answers:yes, no, and I do not know.For each input string, no two pathsmay give contradictory answers,namely both answers yes and no on the same input are not possible.At least one path must give answer yes or no,and if it is yes then the string is considered accepted.SVFA accept the same class of languages as deterministic finite automata (DFA)and NFA but have different state complexity. (en) |
| rdfs:label | Self-verifying finite automaton (en) |
| owl:sameAs | yago-res:Self-verifying finite automaton wikidata:Self-verifying finite automaton https://global.dbpedia.org/id/2qJXY |
| prov:wasDerivedFrom | wikipedia-en:Self-verifying_finite_automaton?oldid=1032064700&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Self-verifying_finite_automaton |
| is dbo:wikiPageRedirects of | dbr:Self-verifying_finite_automata |
| is dbo:wikiPageWikiLink of | dbr:Nondeterministic_finite_automaton dbr:State_complexity dbr:Self-verifying_finite_automata |
| is foaf:primaryTopic of | wikipedia-en:Self-verifying_finite_automaton |