Tree homomorphism

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, a tree homomorphism is a type of homomorphism defined on trees.

Definition[edit]

Given a pair of node-labeled trees and , a mapping from the nodes of to the nodes of is a tree homomorphism if the following conditions hold:

  • maps the root of to the root of ,
  • if node is a child of node in , then is a child of in , and
  • for every node , the label of in is the same as the label of in .

See also[edit]