The translation power of top-down tree-to-graph transducers
From MaRDI portal
Publication:1337465
DOI10.1016/S0022-0000(05)80050-9zbMath0821.68078OpenAlexW1990098162MaRDI QIDQ1337465
Heiko Vogler, Joost Engelfriet
Publication date: 4 December 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80050-9
Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Related Items
Synthesized and inherited functions. A new computational model for syntax-directed semantics, A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead, The generative power of delegation networks, The use of tree transducers to compute translations between graph algebras, Context-free hypergraph grammars have the same term-generating power as attribute grammars, Bottom-up unranked tree-to-graph transducers for translation into semantic graphs, The equivalence of bottom-up and top-down tree-to-graph transducers, Macro tree transducers, attribute grammars, and MSO definable tree translations., Output string languages of compositions of deterministic macro tree transducers
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hyperedge replacement: grammars and languages
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Fundamental properties of infinite trees
- Macro tree transducers
- High level tree transducers and iterated pushdown tree transducers
- Termination of rewriting
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Tree transducers, L systems, and two-way machines
- Attribute grammars and recursive program schemes. I. II
- The string generating power of context-free hypergraph grammars
- Context-free hypergraph grammars have the same term-generating power as attribute grammars
- Surface tree languages and parallel derivation trees
- Top-down tree transducers with deterministic top-down look-ahead
- The complexity of graph languages generated by hyperedge replacement
- Generalized sequential machine maps
- A syntax directed compiler for ALGOL 60
- Graph expressions and graph rewritings
- Proving termination with multiset orderings
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- TOL schemes and control sets
- Bottom-up and top-down tree transformations— a comparison
- Controlled iteration grammars and full hyper-AFL's
- Top-down tree transducers with regular look-ahead
- Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Semantics of context-free languages
- Mappings and grammars on trees
- Translations on a context free grammar
