Deciding origin equivalence of weakly self-nesting macro tree transducers

DOI10.1016/j.ipl.2022.106332OpenAlexW4304080606MaRDI QIDQ2680223

Sebastian Maneth, Helmut Seidl

Publication date: 30 January 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2022.106332

zbMATH Keywords

decidabilityformal languagesmacro tree transducersorigin equivalence

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Deciding equivalence of top-down XML transformations in polynomial time
• Macro forest transducers
• Macro tree transducers
• Decidability of the finiteness of ranges of tree transductions
• Typechecking for XML transformers
• A comparison of pebble tree transducers with macro tree transducers
• Output string languages of compositions of deterministic macro tree transducers
• Decision problems of tree transducers with origin
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Deciding equivalence of separated non-nested attribute systems in polynomial time
• Equivalence of Deterministic Top-Down Tree-to-String Transducers Is Decidable
• Transducers with Origin Information