The equivalence problem for deterministic MSO tree transducers is decidable
From MaRDI portal
Publication:845868
DOI10.1016/J.IPL.2006.05.015zbMATH Open1185.68385arXivcs/0506014OpenAlexW2059690576MaRDI QIDQ845868FDOQ845868
Authors: Joost Engelfriet, Sebastian Maneth 
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.
Full work available at URL: https://arxiv.org/abs/cs/0506014
Recommendations
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- A survey on decidable equivalence problems for tree transducers
- Decidability of equivalence for a class of non-deterministic tree transducers
- Equivalence of deterministic top-down tree-to-string transducers is decidable
- Equivalence of finite-valued tree transducers is decidable
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- scientific article; zbMATH DE number 1500542
- Equivalence problems for tree transducers: a brief survey
- scientific article; zbMATH DE number 125895
- Determinacy and Rewriting of Top-Down and MSO Tree Transformations
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Bounded Algol-Like Languages
- On Context-Free Languages
- Monadic second-order definable graph transductions: a survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Translations on a context free grammar
- A comparison of pebble tree transducers with macro tree transducers
- Typechecking for XML transformers
- The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- Tree transducers, L systems, and two-way machines
- Macro Tree Translations of Linear Size Increase are MSO Definable
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- MSO definable string transductions and two-way finite-state transducers
- 2DST mappings of languages and related problems
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
Cited In (16)
- The equivalence problem for letter-to-letter bottom-up tree transducers is solvable
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- A faithful representation of non-associative Lambek grammars in abstract categorial grammars
- Streaming ranked-tree-to-string transducers
- Determinacy and rewriting of functional top-down and MSO tree transformations
- Decision problems of tree transducers with origin
- Deciding equivalence of linear tree-to-word transducers in polynomial time
- Deciding equivalence of top-down XML transformations in polynomial time
- Earliest normal form and minimization for bottom-up tree transducers
- Copyful streaming string transducers
- Macro Tree Translations of Linear Size Increase are MSO Definable
- Decision problems of tree transducers with origin
- A survey on decidable equivalence problems for tree transducers
- Determinacy and Rewriting of Top-Down and MSO Tree Transformations
- Balancedness of MSO transductions in polynomial time
- Title not available (Why is that?)
Uses Software
This page was built for publication: The equivalence problem for deterministic MSO tree transducers is decidable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845868)
