On the Balancedness of Tree-to-Word Transducers

A language over an alphabet B = A Ā of opening (A) and closing (Ā) brackets, is balanced if it is a subset of the Dyck language B over B, and it is well-formed if all words are prefixes of words in 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. With this at a hand we decide for the class 2-TW of non-linear tree transducers with output alphabet B whether or not the output language is balanced.