Macro tree transducers
Tree transducers are mathematical tools which transform trees into trees. There exist two main categories of such systems: bottom-up (frontier-to- root) tree transducers which process the tree from leaves towards root and top-down (root-to-frontier) tree transducers which work in the opposite direction. Macro tree transducers are a generalization of the top-down tree transducers by considering states of any rank and rules of the form \(q(\sigma (x_ 1,...,x_ m),y_ 1,...,y_ n)\Rightarrow t\) where \(q\in Q\) is a state of rank \(n+1\), \(\sigma\) is a symbol of rank m from the input alphabet \(\Sigma\), \(x_ 1,...,x_ m\) are input variables, \(y_ 1,...,y_ n\) are (formal) parameters and t is a tree over Q and the output alphabet \(\Delta\) of special form. The derivation process is defined in usual way and, similar to context-free tree grammars, we have two restricted derivations: inside-out (IO) derivations and outside-in (IO) derivations. As a practical application, macro tree transducers serve as model for the concept of syntax-directed semantics with context. This paper gives formal definition for macro tree transducers and investigates the properties of induced transformation classes. The connection with context-free tree grammars is studied and the extension with regular look-ahead is considered. The last section contains conclusions and gives valuable ideas for future work.
- A Characterization of Machine Mappings
- A generalized approach to formal languages
- A syntax directed compiler for ALGOL 60
- Algebraic automata and context-free sets
- An order-algebraic definition of Knuthian semantics
- Attribute grammars and recursive program schemes. I. II
- Bottom-up and top-down tree transformation - a comparison
- Bounded nesting in macro grammars
- Composition of top-down and bottom-up tree transductions
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Generalized sequential machine maps
- Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
- Graph grammars and tree transducers
- scientific article; zbMATH DE number 3858450 (Why is no real title available?)
- scientific article; zbMATH DE number 3829278 (Why is no real title available?)
- scientific article; zbMATH DE number 3716833 (Why is no real title available?)
- scientific article; zbMATH DE number 3540387 (Why is no real title available?)
- Hypergrammars: An extension of macrogrammars
- Initial Algebra Semantics and Continuous Algebras
- IO and OI. II
- Mappings and grammars on trees
- Nested Stack Automata
- On the power of list iteration
- Semantics of context-free languages: Correction
- The copying power of one-state tree transducers
- The formal power of one-visit attribute grammars
- The IO- and OI-hierarchies
- Three hierarchies of transducers
- Top-down tree transducers with regular look-ahead
- Translations on a context free grammar
- Tree transducers, L systems, and two-way machines
- Deciding equivalence of top-down XML transformations in polynomial time
- Macro forest transducers
- Pushdown machines for the macro tree transducer
- High level tree transducers and iterated pushdown tree transducers
- A characterization of attributed tree transformations by a subclass of macro tree transducers
- Functional description of the contextual analysis in block-structured programming languages: A case study of tree transducers
- Top-down tree transducers with two-way tree walking look-ahead
- An implementation of syntax directed functional programming on nested- stack machines
- Context-free hypergraph grammars have the same term-generating power as attribute grammars
- Tree transducers with external functions
- Decidability of the finiteness of ranges of tree transductions
- The equivalence of bottom-up and top-down tree-to-graph transducers
- On injectivity of deterministic top-down tree transducers
- The translation power of top-down tree-to-graph transducers
- Synthesized and inherited functions. A new computational model for syntax-directed semantics
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- Output string languages of compositions of deterministic macro tree transducers
- 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.
- The complexity of the exponential output size problem for top-down and bottom-up tree transducers
- An operational and denotational approach to non-context-freeness
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- Static garbage collection
- Backward type inference for XML queries
- XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
- Composing stack-attributed tree transducers
- Modulo constraints and the complexity of typechecking XML views
- Closure properties of linear context-free tree languages with an application to optimality theory
- A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead
- Deciding origin equivalence of weakly self-nesting macro tree transducers
- Characterizing important subclasses of attributed tree transformations by macro tree transducers
- A survey on decidable equivalence problems for tree transducers
- Regular Programming for Quantitative Properties of Data Streams
- Deciding equivalence of linear tree-to-word transducers in polynomial time
- Visibly pushdown transducers with look-ahead
- A mechanized theory of regular trees in dependent type theory
- Join-Lock-Sensitive Forward Reachability Analysis for Concurrent Programs with Dynamic Process Creation
- Tree transformations and dependencies
- scientific article; zbMATH DE number 3858450 (Why is no real title available?)
- scientific article; zbMATH DE number 3866600 (Why is no real title available?)
- An Algebra for Tree-Based Music Generation
- Algebraic fusion of functions with an accumulating parameter and its improvement
- scientific article; zbMATH DE number 5506094 (Why is no real title available?)
- Multi-Return Macro Tree Transducers
- Monadic Datalog Tree Transducers
- scientific article; zbMATH DE number 3965457 (Why is no real title available?)
- scientific article; zbMATH DE number 3972227 (Why is no real title available?)
- Iterated linear control and iterated one-turn pushdowns
- scientific article; zbMATH DE number 4041320 (Why is no real title available?)
- Syntax-directed semantics. Formal models based on tree transducers
- scientific article; zbMATH DE number 475423 (Why is no real title available?)
- Macro Tree Translations of Linear Size Increase are MSO Definable
- The use of tree transducers to compute translations between graph algebras
- A hierarchy of deterministic top-down tree transformations
- scientific article; zbMATH DE number 7559409 (Why is no real title available?)
- scientific article; zbMATH DE number 7561353 (Why is no real title available?)
- The equivalence problem for letter-to-letter bottom-up tree transducers is solvable
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Polynomial-time inverse computation for accumulative functions with multiple data traversals
- Context-free grammars on trees
- Categorical Views on Computations on Trees (Extended Abstract)
- Circularity, composition, and decomposition results for pebble macro tree transducers
- On the complexity of typechecking top-down XML transformations
- Verification of tree-processing programs via higher-order model checking
- Basic tree transducers
- Look-ahead on pushdowns
- A pumping lemma for output languages of macro tree transducers
- Streaming ranked-tree-to-string transducers
- Characterizing attributed tree translations in terms of macro tree transducers
- Deterministic top-down tree transducers with iterated look-ahead
- 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
- Storage-to-tree transducers with look-ahead
- Comparison-free polyregular functions
- Determinacy and rewriting of functional top-down and MSO tree transformations
- Modular tree transducers
- On the tree-transformation power of XSLT
- Deaccumulation techniques for improving provability
- The generative power of delegation networks
- Look-ahead removal for total deterministic top-down tree transducers
- A complete rewriting system for a monoid of tree transformation classes
This page was built for publication: Macro tree transducers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1073576)