Macro Tree Translations of Linear Size Increase are MSO Definable
From MaRDI portal
(Redirected from Publication:4429669)
Recommendations
- scientific article; zbMATH DE number 1500542
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- scientific article; zbMATH DE number 3866600
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- Macro tree transducers
- The equivalence problem for deterministic MSO tree transducers is decidable
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Extension complexity, MSO logic, and treewidth
Cited in
(26)- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- Decision problems of tree transducers with origin
- Visibly pushdown transducers
- Multiple context-free tree grammars: lexicalization and characterization
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- Recognizability, hypergraph operations, and logical types
- Linking theorems for tree transducers
- A survey on decidable equivalence problems for tree transducers
- Deciding equivalence of linear tree-to-word transducers in polynomial time
- Earliest normal form and minimization for bottom-up tree transducers
- Tree transformations and dependencies
- Decision problems of tree transducers with origin
- scientific article; zbMATH DE number 1500542 (Why is no real title available?)
- GETGRATS: a summary of scientific results (with annotated bibliography)
- Copyful streaming string transducers
- scientific article; zbMATH DE number 7561353 (Why is no real title available?)
- Composition closure of linear extended top-down tree transducers
- Polynomial-time inverse computation for accumulative functions with multiple data traversals
- Deciding whether an attributed translation can be realized by a top-down transducer
- Deciding whether an attributed translation can be realized by a top-down transducer
- Shape preserving tree transducers
- Deciding linear height and linear size-to-height increase of macro tree transducers
- Determinacy and rewriting of functional top-down and MSO tree transformations
- The equivalence problem for deterministic MSO tree transducers is decidable
- Automata for XML -- a survey
This page was built for publication: Macro Tree Translations of Linear Size Increase are MSO Definable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429669)
