The translation power of top-down tree-to-graph transducers

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

zbMATH Keywords

hypergraphtop-down tree-to-graph transducer

Mathematics Subject Classification ID

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

• ALGOL 60

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