On the Balancedness of Tree-to-word Transducers

2019/11/29 by Raphaela Löbel, Löbel, Raphaela, Michael Luttenberger +3
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL

paper · pdf · doi:10.48550/arxiv.1911.13054

Major changes in Section 3 Balancedness of 2-TWs: instead of proving equivalence of LTWs over the involutive monoid we use the result that equivalence of LTWs over the free group is decidable in polynomial time (arXiv:2001.03480). A short version will be published in the conference proceedings of DLT 2020

arxiv created 2020/03/13 · arxiv updated 2020/03/16

Abstract

A language over an alphabet B = A ∪ A of opening (A) and closing (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. With this at a hand we decide for the class 2-TWs of non-linear tree transducers with output alphabet B^* whether or not the output language is balanced.

Citations

• Equivalence of Linear Tree Transducers with Output in the Free Group

Related

• Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time
• Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
• Composition Closure of Linear Extended Top-down Tree Transducers
• Balancing Straight-Line Programs
• Improved bounds for testing Dyck languages