3 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…
math.GR2025
On groups with EDT0L word problem
Alex Bishop, Murray Elder, Alex Evetts +2
We prove that the word problem for the infinite cyclic group is not EDT0L, and obtain as a corollary that a finitely generated group with EDT0L word problem must be torsion. In add…
cs.FL2025
The structure of polynomial growth for tree automata/transducers and MSO set queries
Paul Gallot, Nathan Lhote, Lê Thành Dũng Nguyên
Given an -weighted tree automaton, we give a decision procedure for exponential vs polynomial growth (with respect to the input size) in quadratic time, and an algorith…