3 papers
math.GR2026
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.FL2026
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…
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…