Macro Tree Translations of Linear Size Increase are MSO Definable

DOI10.1137/S0097539701394511zbMath1029.68090OpenAlexW1983214696MaRDI QIDQ4429669

Sebastian Maneth, Joost Engelfriet

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539701394511

zbMATH Keywords

monadic second-order logicdecidabilitytree transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42)

Related Items

Decision Problems of Tree Transducers with Origin ⋮ Linking theorems for tree transducers ⋮ Tree Transformations and Dependencies ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ Decision problems of tree transducers with origin ⋮ EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS ⋮ Visibly pushdown transducers ⋮ Automata for XML -- a survey ⋮ Deciding whether an attributed translation can be realized by a top-down transducer ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Composition closure of linear extended top-down tree transducers ⋮ Polynomial-time inverse computation for accumulative functions with multiple data traversals ⋮ GETGRATS ⋮ Recognizability, hypergraph operations, and logical types ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time ⋮ Copyful Streaming String Transducers