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 $\varphi$ from the nodes of $T_1$ to the nodes of $T_2$ is a tree homomorphism if the following conditions hold:

• $\varphi$ 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 $\varphi (n_2)$ is a child of $\varphi (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 $\varphi (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)

• HeyLink.me
• Outline (list)
• Sentinel node
• Dynamic syntax tree

---