2026-08-19T03:39:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22965 2025-03-21T09:58:46Z ddc:004 open_access

Learning Tree Pattern Transformations Neider, Daniel Sabellek, Leif Schmidt, Johannes Vehlken, Fabian Zeume, Thomas Tree pattern transformations learning from positive examples computational complexity Explaining why and how a tree t structurally differs from another tree t^⋆ 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 {(t₁, t₁^⋆),… , (t_n, t_n^⋆)} of pairs of labelled, ordered trees; is there a small set of rules that explains the structural differences between all pairs (t_i, t_i^⋆)? 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Neider and Leif Sabellek and Johannes Schmidt and Fabian Vehlken and Thomas Zeume 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.24 urn:nbn:de:0030-drops-229652 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.24 eng https://creativecommons.org/licenses/by/4.0/legalcode