The equivalence problem for deterministic MSO tree transducers is decidable
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 3714978 (Why is no real title available?)
- scientific article; zbMATH DE number 3622977 (Why is no real title available?)
- scientific article; zbMATH DE number 1200800 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3293666 (Why is no real title available?)
- 2DST mappings of languages and related problems
- 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
- Bounded Algol-Like Languages
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- MSO definable string transductions and two-way finite-state transducers
- Macro Tree Translations of Linear Size Increase are MSO Definable
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Monadic second-order definable graph transductions: a survey
- On Context-Free Languages
- On the equivalence problem for attribute systems
- The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
- The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- Translations on a context free grammar
- Tree transducers, L systems, and two-way machines
- Typechecking for XML transformers
Cited in
(16)- Copyful streaming string transducers
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Macro Tree Translations of Linear Size Increase are MSO Definable
- Streaming ranked-tree-to-string transducers
- The equivalence problem for letter-to-letter bottom-up tree transducers is solvable
- A survey on decidable equivalence problems for tree transducers
- scientific article; zbMATH DE number 7559409 (Why is no real title available?)
- Determinacy and Rewriting of Top-Down and MSO Tree Transformations
- Deciding equivalence of linear tree-to-word transducers in polynomial time
- Deciding equivalence of top-down XML transformations in polynomial time
- Determinacy and rewriting of functional top-down and MSO tree transformations
- A faithful representation of non-associative Lambek grammars in abstract categorial grammars
- Earliest normal form and minimization for bottom-up tree transducers
- Decision problems of tree transducers with origin
- Decision problems of tree transducers with origin
- Balancedness of MSO transductions in polynomial time
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)
