Tree homomorphism

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

Definition

Given a pair of rooted node-labeled trees $T_{1}$ and $T_{2}$, a mapping $\phi$ from the nodes of $T_{1}$ to the nodes of $T_{2}$ is a tree homomorphism if the following conditions hold:

• $\phi$ maps the root of $T_{1}$ to the root of $T_{2}$,
• if node $n_{2}$ is a child of node $n_{1}$ in $T_{1}$, then $\phi (n_{2})$ is a child of $\phi (n_{1})$ in $T_{2}$, and
• for every node $n\in T_{1}$, the label of $n$ in $T_{1}$ is the same as the label of $\phi (n)$ in $T_{2}$.

See also

• Homomorphism

This article "Tree homomorphism" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Tree homomorphism. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Outline (list)
• Dynamic syntax tree

---