TY - GEN
T1 - On the Balancedness of Tree-to-Word Transducers
AU - Löbel, Raphaela
AU - Luttenberger, Michael
AU - Seidl, Helmut
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - A language over an alphabet (Formula Presented) of opening (A) and closing (A) brackets, is balanced if it is a subset of the Dyck language DB over B, and it is well-formed if all words are prefixes of words in DB. 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.
AB - A language over an alphabet (Formula Presented) of opening (A) and closing (A) brackets, is balanced if it is a subset of the Dyck language DB over B, and it is well-formed if all words are prefixes of words in DB. 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.
KW - Balancedness of tree-to-word transducer
KW - Equivalence
KW - Longest common suffix/prefix of a CFG
UR - http://www.scopus.com/inward/record.url?scp=85086182102&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-48516-0_17
DO - 10.1007/978-3-030-48516-0_17
M3 - Conference contribution
AN - SCOPUS:85086182102
SN - 9783030485153
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 222
EP - 236
BT - Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings
A2 - Jonoska, Nataša
A2 - Savchuk, Dmytro
PB - Springer
T2 - 24th International Conference on Developments in Language Theory, DLT 2020
Y2 - 11 May 2020 through 15 May 2020
ER -