The equivalence problem for deterministic MSO tree transducers is decidable

DOI10.1016/j.ipl.2006.05.015zbMath1185.68385arXivcs/0506014OpenAlexW2059690576MaRDI QIDQ845868

Joost Engelfriet, Sebastian Maneth

Publication date: 29 January 2010

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

Full work available at URL: https://arxiv.org/abs/cs/0506014

zbMATH Keywords

automata theoryformal languagesequivalence problemtransducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Decision Problems of Tree Transducers with Origin, Decision problems of tree transducers with origin, EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS, A faithful representation of non-associative Lambek grammars in abstract categorial grammars, Unnamed Item, Determinacy and rewriting of functional top-down and MSO tree transformations, A Survey on Decidable Equivalence Problems for Tree Transducers, Streaming ranked-tree-to-string transducers, Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time, Deciding equivalence of top-down XML transformations in polynomial time, Copyful Streaming String Transducers

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tree transducers, L systems, and two-way machines
• 2DST mappings of languages and related problems
• Monadic second-order definable graph transductions: a survey
• Typechecking for XML transformers
• A comparison of pebble tree transducers with macro tree transducers
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• On the equivalence problem for attribute systems
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
• MSO definable string transductions and two-way finite-state transducers
• Macro Tree Translations of Linear Size Increase are MSO Definable
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Bounded Algol-Like Languages
• On Context-Free Languages
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Translations on a context free grammar
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science