On the Balancedness of Tree-to-word Transducers

A language over an alphabet $B=A\cup\overline{A}$ of opening ($A$) and closing ($\overline{A}$) brackets, is balanced if it is a subset of the Dyck language $D_{B}$ over $B$, and it is well-formed if all words are prefixes of words in $D_{B}$. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. We also show that equivalence of linear tree transducers with well-formed output in $B^*$ is decidable in polynomial time. These two results enable us to decide in polynomial time for the class 2-TW of non-linear tree transducers with output alphabet $B^*$ whether or not the output language is balanced.