Abstract
Unordered trees are significant in applications where the order among child vertices is insignificant, such as abstract syntax trees and chemical structures. To describe patterns in such trees, we propose unordered term tree patterns that utilize height-constrained variables to restrict trunk length and subtree height. We formalize the pattern matching problem between an unordered term tree pattern and an unordered tree, presenting an $O(N \cdot \max\{nD^{3/2}, \mathcal{S}\})$-time algorithm, where $n$ and $N$ are the numbers of vertices in the pattern and tree, $D$ is the maximum vertex degree, and $\mathcal{S}$ is the sum of trunk constraints. Computational results show that the algorithm runs efficiently in practice.
Blogger's Review: This algorithm effectively addresses the pattern matching issue in unordered trees by introducing height-constrained variables, showcasing potential in specific application scenarios, especially for complex tree structures. Its time complexity design considers various factors, making the algorithm highly feasible for practical use.