About: Computation tree

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input. A computation tree is a rooted tree of nodes and edges. Each node in the tree represents a single computational state, while each edge represents a transition to the next possible computation. The number of nodes of the tree is the size of the tree and the length of the path from the root to a given node is the depth of the node. The largest depth of an output node is the depth of the tree. The leaves of the tree are called output nodes.

Property Value
dbo:abstract
  • A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input. A computation tree is a rooted tree of nodes and edges. Each node in the tree represents a single computational state, while each edge represents a transition to the next possible computation. The number of nodes of the tree is the size of the tree and the length of the path from the root to a given node is the depth of the node. The largest depth of an output node is the depth of the tree. The leaves of the tree are called output nodes. In a computation tree for a decision problem, each output node is labeled Yes or No. If a tree, T, with an input space X, if and the path for x ends in node labeled yes, then the input x is accepted. Else it is rejected. The depth of the computation tree for a given input is the computation time for the Turing machine on that input. Computation trees have also been used to study the computational complexity of problems in computational geometry and real number calculations. (en)
dbo:wikiPageID
  • 3365796 (xsd:integer)
dbo:wikiPageLength
  • 2245 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 933073982 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input. A computation tree is a rooted tree of nodes and edges. Each node in the tree represents a single computational state, while each edge represents a transition to the next possible computation. The number of nodes of the tree is the size of the tree and the length of the path from the root to a given node is the depth of the node. The largest depth of an output node is the depth of the tree. The leaves of the tree are called output nodes. (en)
rdfs:label
  • Computation tree (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License