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

DOI10.1007/BF01178504MaRDI QIDQ1199703zbMATH OpenOpenAlexFDO

Authors 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 grammarscontext-free hypergraph grammarsemantic domainsyntax-directed translation deviceterm languages

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 1268708
• scientific article; zbMATH DE number 177442
• The string generating power of context-free hypergraph grammars
• Publication:4376265
• Contextual Hypergraph Grammars – A New Approach to the Generation of Hypergraph Languages
• Context-free hypergraph grammars with node rewriting
• scientific article; zbMATH DE number 177438
• A comparison of boundary graph grammars and context-free hypergraph grammars
• The generative power of context-free node rewriting in hypergraphs
• Powerful and NP-complete: hypergraph Lambek grammars

Cites work

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

Cited in

(18)

• The string generating power of context-free hypergraph grammars
• The equivalence of bottom-up and top-down tree-to-graph transducers
• The generating power of total deterministic tree transducers
• Hypergraph languages of bounded degree
• 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
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Multiple context-free tree grammars: lexicalization and characterization
• Handle-rewriting hypergraph grammars
• Towards more precise rewriting approximations
• scientific article; zbMATH DE number 4080942 (Why is no real title available?)
• scientific article; zbMATH DE number 177442 (Why is no real title available?)
• scientific article; zbMATH DE number 1268708 (Why is no real title available?)
• scientific article; zbMATH DE number 1116593 (Why is no real title available?)
• Graphs and designing
• A Greibach normal form for context-free graph grammars
• The generative power of delegation networks

This page was built for publication: Context-free hypergraph grammars have the same term-generating power as attribute grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199703)