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 $\mathbb{N}$-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…