1 citations · 1 across the 3 of their papers we have counts for
4 papers
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…
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…
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…
Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
Paul Gallot, Sebastian Maneth, Keisuke Nakano +1
We present a novel normal form for (total deterministic) macro tree transducers (mtts), called depth proper normal form. If an mtt is in this normal form, then it is guaranteed tha…