EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS

DOI10.1142/S012905411100891XzbMath1252.68170OpenAlexW2153107566MaRDI QIDQ2909099

Sebastian Maneth, Sylvia Friese, Helmut Seidl

Publication date: 29 August 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905411100891x

zbMATH Keywords

normal formminimizationbottom-up tree transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A Survey on Decidable Equivalence Problems for Tree Transducers

Cites Work

• Single-valuedness of tree transducers is decidable in polynomial time
• The equivalence problem for deterministic MSO tree transducers is decidable
• Deciding equivalence of top-down XML transformations in polynomial time
• Minimization algorithms for sequential transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Attributed tree transducers cannot induce all deterministic bottom-up tree transformations
• Generalized sequential machine maps
• On the equivalence problem for attribute systems
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• Macro Tree Translations of Linear Size Increase are MSO Definable
• DECIDABILITY OF THE SHAPE PRESERVING PROPERTY OF BOTTOM-UP TREE TRANSDUCERS
• Semantics of context-free languages
• Mappings and grammars on trees
• Translations on a context free grammar