# Learning Tree Pattern Transformations

arXiv: https://arxiv.org/abs/2410.07708 · HTML: https://mlsanity.com/paper/2410.07708/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 32 references that are in the map.
- First posted on arXiv 10 Oct 2024.

## Builds on (most cited first, 3 of 3)

- [Learning Linear Temporal Properties](https://mlsanity.com/paper/1806.03953/) (2018)
- [Learning Interpretable Temporal Properties from Positive Examples Only](https://mlsanity.com/paper/2209.02650/) (2022)
- [Learning Interpretable Models in the Property Specification Language](https://mlsanity.com/paper/2002.03668/) (2020)

## Abstract (arXiv)

Explaining why and how a tree t structurally differs from another tree t^star is a question that is encountered throughout computer science, including in understanding tree-structured data such as XML or JSON data. In this article, we explore how to learn explanations for structural differences between pairs of trees from sample data: suppose we are given a set (t1, t1^star),dots, (tn, tn^star) of pairs of labelled, ordered trees; is there a small set of rules that explains the structural differences between all pairs (ti, ti^star)? This raises two research questions: (i) what is a good notion of "rule" in this context?; and (ii) how can sets of rules explaining a data set be learned algorithmically? We explore these questions from the perspective of database theory by (1) introducing a pattern-based specification language for tree transformations; (2) exploring the computational complexity of variants of the above algorithmic problem, e.g. showing NP-hardness for very restricted variants; and (3) discussing how to solve the problem for data from CS education research using SAT solvers.