Context-Free Graph Grammars: Separating Vertex Replacement from Hyperedge Replacement
作者： Bruno Courcelle
关键词:
摘要: We establish that a set of graphs generated by “Vertex replacement” graph grammar can be “Hyperedge one iff its do not contain arbitrarily large complete bipartite Kn,n as subgraphs, have number edges is linearly bounded in terms the vertices. These properties are decidable means an appropriate extension theorem Parikh characterizes commutative images context-free languages.
springer.com
sci-hub.st 参考文章(22)
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
Bruno Courcelle, Monadic second-order definable graph transductions CAAP '92. pp. 124- 144 ,(1992) , 10.1007/3-540-55251-0_7
Bruno Courcelle, Graph grammars, monadic second-order logic and the theory of graph minors. Graph Structure Theory. pp. 565- 590 ,(1991)
A. Habel, Hyperedge Replacement: Grammars and Languages ,(1992)
Franz J. Brandenburg, The equivalence of boundary and confluent graph grammars on graph languages of bounded degree rewriting techniques and applications. pp. 312- 322 ,(1991) , 10.1007/3-540-53904-2_106
G. Rozenberg, The Book of L ,(1986)
Bruno COURCELLE, Graph rewriting: an algebraic and logic approach Handbook of theoretical computer science (vol. B). pp. 193- 242 ,(1991) , 10.1016/B978-0-444-88074-1.50010-X
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
Joost Engelfriet, Context-Free NCE Graph Grammars fundamentals of computation theory. pp. 148- 161 ,(1989) , 10.1007/3-540-51498-8_15
Bruno Courcelle, The monadic second-order logic of graphs V: on closing the gap between definability and recognizability mathematical foundations of computer science. ,vol. 80, pp. 152- 202 ,(1991) , 10.1016/0304-3975(91)90387-H