Handle-rewriting hypergraph grammars

作者: Bruno Courcelle , Joost Engelfriet , Grzegorz Rozenberg

DOI: 10.1016/0022-0000(93)90004-G

关键词:

摘要: Abstract We introduce the handle-rewriting hypergraph grammars (HH grammars), based on replacement of handles, i.e., subhypergraphs consisting one hyperedge together with its incident vertices. This extends replacement, where only is replaced. A HH grammar separated (an S-HH grammar) if nonterminal handles do not overlap. The are context-free, and sets they generate can be characterized as least solutions certain systems equations. They same graphs NLC-like vertex-rewriting C-edNCE graph that also context-free.

参考文章(35)
D. Janssens, G. Rozenberg, A Survey of NLC Grammars colloquium on trees in algebra and programming. pp. 114- 128 ,(1983) , 10.1007/3-540-12727-5_5
Clemens Lautemann, Efficient algorithms on context-free graph languages international colloquium on automata, languages and programming. pp. 362- 378 ,(1988) , 10.1007/3-540-19488-6_128
B. Courcelle, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues Theoretical Informatics and Applications. ,vol. 26, pp. 257- 286 ,(1992) , 10.1051/ITA/1992260302571
Joost Engelfriet, George Leih, Grzegorz Rozenberg, Apex Graph Grammars international workshop on graph grammars and their application to computer science. pp. 167- 185 ,(1986) , 10.1007/3-540-18771-5_52
Bruno Courcelle, The Monadic Second-Order Logic of Graphs: Definable Sets of Finite Graphs workshop on graph theoretic concepts in computer science. pp. 30- 53 ,(1988) , 10.1007/3-540-50728-0_34
Ugo Montanari, Francesca Rossi, An Efficient Algorithm for the Solution of Hierarchical Networks of Constraints international workshop on graph grammars and their application to computer science. pp. 440- 457 ,(1986) , 10.1007/3-540-18771-5_69
Joost Engelfriet, A Characterization of Context-Free NCE Graph Languages by Monadic Second-Order Logic on Trees international workshop on graph grammars and their application to computer science. pp. 311- 327 ,(1990) , 10.1007/BFB0017397
Bruno Courcelle, Joost Engelfriet, Grzegorz Rozenberg, Context-free Handle-rewriting Hypergraph Grammars international workshop on graph grammars and their application to computer science. pp. 253- 268 ,(1990) , 10.1007/BFB0017394