Efficient Pattern Matching for Unordered Term Tree Patterns under Generalized Height-Constrained Bindings
arXiv:2607.14617
The paper presents a polynomial‑time algorithm for matching unordered term tree patterns with height‑constrained variables under a generalized binding model, and validates its practical performance through implementation and experiments.
Abstract
Unordered trees are useful for modeling hierarchical structures in which the order among siblings is irrelevant. To represent flexible structural patterns in such data, unordered term tree patterns with height-constrained variables provide a natural framework. In our previous work, we studied the pattern matching problem for rooted unordered term tree patterns with height-constrained variables under the restriction that the child port of each variable must correspond to a leaf of a binding tree. In this paper, we remove this restriction and generalize the binding model so that the child port may correspond to any non-root vertex of a binding tree. Under generalized bindings, we formulate the corresponding membership problem and present a polynomial-time pattern matching algorithm. We also implement the proposed algorithm and conduct computational experiments to evaluate its running time. The experimental results show that the proposed method achieves practical running times.
6 pages, 2 figures. Author preprint of a paper presented at ESKM 2026, IIAI-AAI 2026