Computation tree

Computation tree

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 output nodes of the tree are called leaves.

In a computation tree each output node is labeled Yes or No. If a tree, T, with an input space X, if x \in X 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.

One of the primary methods of showing that a computational problem L is complete for a given complexity class C is to show that the computation tree of any algorithm in C can be directly analyzed in terms of L.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Computation tree logic — Computation tree logic (CTL) is a branching time logic, meaning that its model of time is a tree like structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is… …   Wikipedia

  • Computation Tree Logic — Die Computation Tree Logic (kurz CTL) ist eine Temporale Logik, die speziell zur Spezifikation und Verifikation von Computersystemen dient. Meist wird sie auch mit CTL* bezeichnet. CTL bezeichnet dann eine spezielle Teilmenge der CTL* Formeln.… …   Deutsch Wikipedia

  • Computation Tree Logic* — Die Computation Tree Logic (kurz CTL) ist eine Temporale Logik, die speziell zur Spezifikation und Verifikation von Computersystemen dient. Meist wird sie auch mit CTL* bezeichnet. CTL bezeichnet dann eine spezielle Teilmenge der CTL* Formeln.… …   Deutsch Wikipedia

  • computation tree logic — noun A particular modal logic of branching time with operators next , globally , finally or eventually , until , and weak until . Syn: computational tree logic, CTL …   Wiktionary

  • Computation time — In computational complexity theory, computation time is a measure of how many steps are used by some abstract machine in a particular computation. For any given model of abstract machine, the computation time used by that abstract machine is a… …   Wikipedia

  • Computational tree logic — Computation tree logic (CTL) is a branching time logic, meaning that its model of time is a tree like structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is… …   Wikipedia

  • Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia

  • Tree rotation — A tree rotation is an operation on a binary search tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. They are used to change the shape of the tree …   Wikipedia

  • Decision tree model — In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is considered to be basically a decision tree, i.e., a sequence… …   Wikipedia

  • Spanning tree protocol — The Spanning Tree Protocol is an OSI layer 2 protocol that ensures a loop free topology for any bridged LAN. It is based on an algorithm invented by Radia Perlman while working for Digital Equipment Corporationcite… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”