2 papers
cs.FL2025
Shape Preserving Tree Transducers
Paul Gallot, Sebastian Maneth
It is shown that shape preservation is decidable for top-down tree transducers, bottom-up tree transducers, and for compositions of total deterministic macro tree transducers. More…
cs.LO2025
FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
Markus Lohrey, Sebastian Maneth, Markus L. Schmid
Enumerating the result set of a first-order query over a relational structure of bounded degree can be done with linear preprocessing and constant delay. In this work, we extend th…