Metraipolis › archive › dc_cb2b2c489a54
Type-Checking for Pattern-Based Tree Transformations — arXiv:2610.11337
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.11337
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:13:48.138Z
- SHA-256 of the archived text
4b68ed9848151c2a4eadcd5286d70f8252ad6fe294ced2e5d97f8760989b1633- Stable URL of this page
https://metraipolis.com/documento/dc_cb2b2c489a54
How to cite
Type-Checking for Pattern-Based Tree Transformations — arXiv:2610.11337 — arXiv (en), https://arxiv.org/abs/2610.11337 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cb2b2c489a54 (Metraipolis archive dc_cb2b2c489a54, sha256 4b68ed9848151c2a4eadcd5286d70f8252ad6fe294ced2e5d97f8760989b1633)
BibTeX
@misc{dccb2b2c489a54,
title = {Type-Checking for Pattern-Based Tree Transformations — arXiv:2610.11337},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.11337},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cb2b2c489a54; sha256 4b68ed9848151c2a4eadcd5286d70f8252ad6fe294ced2e5d97f8760989b1633},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11337. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce and study pattern-based tree transformations. As an illustrating example, consider a source pattern $(x \cdot y) + (x \cdot z)$ and a target pattern $x \cdot (y + z)$ as a pair. This source pattern matches any expression $e$ of the form $(e_1 \cdot e_2) + (e_1 \cdot e_3)$ (by substituting $x$ with $e_1$, $y$ with $e_2$, and $z$ with $e_3$) and the pair transforms it into the expression $e_1 \cdot (e_2 + e_3)$ as dictated by the target pattern. Note that in this example, the set of expressions that match the source pattern is not a regular tree language. We propose a model of tree transformations given by a finite representation of a (possibly infinite) set of such (source pattern, target pattern) pairs. The expressive power of this model comes at the cost of undecidability of checking equivalence. Nevertheless, we show that the type-checking problem is decidable for our model of pattern-based tree transformations. The type-checking problem asks whether applying a given transformation to trees having a given regular property (type) preserves the property. Our decision procedure is by a reduction to the emptiness problem of alternating tree automata. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.CL, nuovi lavori del giorno). Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Computation and Language (cs.CL). Pagina del lavoro: https://arxiv.org/abs/2610.11337 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T05:47:15.493Z dalla pagina https://arxiv.org/list/cs.CL/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).