Context-free hypergraph grammars have the same term-generating power as attribute grammars

DOI10.1007/BF01178504zbMath0769.68072OpenAlexW2041988689MaRDI QIDQ1199703

Joost Engelfriet, Linda Heyker

Publication date: 16 January 1993

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01178504

zbMATH Keywords

attribute grammarssemantic domaincontext-free hypergraph grammarsyntax-directed translation deviceterm languages

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Handle-rewriting hypergraph grammars, The translation power of top-down tree-to-graph transducers, Context-free graph languages of bounded degree are generated by apex graph grammars, Synthesized and inherited functions. A new computational model for syntax-directed semantics, Graphs and designing, The generative power of delegation networks, Towards more precise rewriting approximations, Multiple context-free tree grammars: lexicalization and characterization, A Greibach normal form for context-free graph grammars, The equivalence of bottom-up and top-down tree-to-graph transducers, The generating power of total deterministic tree transducers, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Hypergraph languages of bounded degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Macro tree transducers
• Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• The formal power of one-visit attribute grammars
• Attribute grammars and recursive program schemes. I. II
• Interpretation and reduction of attribute grammars
• The string generating power of context-free hypergraph grammars
• Attribute grammars. Definitions, systems and bibliography
• The translation power of top-down tree-to-graph transducers
• Plex languages
• Pair grammars, graph languages and string-to-graph translations
• Proofs of partial correctness for attribute grammars with applications to recursive procedures and logic programming
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Relating logic programs and attribute grammars
• The Complexity of Languages Generated by Attribute Grammars
• Graph expressions and graph rewritings
• Semantic evaluation from left to right
• IO-macrolanguages and attributed translations
• Algebraic automata and context-free sets
• Semantics of context-free languages