2013/01/08 by Zoltán Fülöp, Fülöp, Zoltán, Andreas Maletti +1
Computer Science · #68Q42 #68Q45 #Algorithms and Data Compression #F.4.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #acm:68Q42 #acm:68Q45 #cs.FL #msc:68Q42 #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1301.1514
21 pages, 7 figures, 4 tables
arxiv created 2013/01/08 · openalex publication_date 2013/01/08 · arxiv updated 2013/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Linear extended top-down tree transducers (or synchronous tree-substitution grammars) are popular formal models of tree transformations. The expressive power of compositions of such transducers with and without regular look-ahead is investigated. In particular, the restrictions of nondeletion, epsilon-freeness, and strictness are considered. The composition hierarchy turns out to be finite for all epsilon-free (all rules consume input) variants of these transducers except for nondeleting epsilon-free linear extended top-down tree transducers. The least number of transducers needed for the full expressive power of arbitrary compositions is presented. In all remaining cases (including nondeleting epsilon-free linear extended top-down tree transducers) the composition hierarchy does not collapse.