A Survey on Decidable Equivalence Problems for Tree Transducers
From MaRDI portal
Publication:2800413
DOI10.1142/S0129054115400134zbMath1345.68212MaRDI QIDQ2800413
Publication date: 15 April 2016
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
surveyequivalencemonadic second-order logicdecidabilitytop-down tree transducertree transducermacro tree transducerParikh
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Related Items (8)
Definability results for top-down tree transducers ⋮ How to decide functionality of compositions of top-down tree transducers ⋮ Definability Results for Top-Down Tree Transducers ⋮ Functionality of compositions of top-down tree transducers is decidable ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ Streaming ranked-tree-to-string transducers
Cites Work
- On the complexity of typechecking top-down XML transformations
- 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
- Macro forest transducers
- Macro tree transducers
- Tree transducers, L systems, and two-way machines
- The IO- and OI-hierarchies
- Attribute grammars and recursive program schemes. I. II
- Functional description of the contextual analysis in block-structured programming languages: A case study of tree transducers
- Alphabetic tree relations
- On the decidability of the sequence equivalence problem for DOL-systems
- On the equivalence problem for letter-to-letter top-down tree transducers
- Monadic second-order definable graph transductions: a survey
- Haskell overloading is DEXPTIME-complete
- Typechecking for XML transformers
- A comparison of pebble tree transducers with macro tree transducers
- A short solution for the HDT0L sequence equivalence problem
- Output string languages of compositions of deterministic macro tree transducers
- Minimizing subsequential transducers: a survey.
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Polynomial size test sets for context-free languages
- Generalized sequential machine maps
- EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS
- On the equivalence problem for attribute systems
- The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
- The intrinsically exponential complexity of the circularity problem for attribute grammars
- Bottom-up and top-down tree transformations— a comparison
- The decidability of the equivalence problem for DOL-systems
- Top-down tree transducers with regular look-ahead
- Equivalence of finite-valued tree transducers is decidable
- Macro Tree Translations of Linear Size Increase are MSO Definable
- On Context-Free Languages
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- Semantics of context-free languages
- Indexed Grammars—An Extension of Context-Free Grammars
- Mappings and grammars on trees
- Translations on a context free grammar
This page was built for publication: A Survey on Decidable Equivalence Problems for Tree Transducers
