Monadic second-order evaluations on tree-decomposable graphs
作者： B. Courcelle , M. Mosbah
DOI: 10.1016/0304-3975(93)90064-Z
关键词: Discrete mathematics 、 Homomorphism 、 Combinatorics 、 Second-order logic 、 Large class 、 Courcelle's theorem 、 Mathematics 、 Semiring 、 Graph 、 Formalism (philosophy of mathematics)
摘要: Abstract Every graph generated by a hyperedge replacement graph-grammar can be represented tree, namely the derivation tree of sequence that produced it. Certain functions on graphs computed recursively trees these graphs. By using monadic second-order logic and semiring homomorphisms, we describe in single formalism large class such functions. Polynomial even linear algorithms constructed for some We unify similar results obtained Takamizawa (1982), Bern (1987), Arnborg (1991) Habel (1989).
elsevier.com
sci-hub.se 参考文章(22)
Bruno Courcelle, Monadic second-order definable graph transductions CAAP '92. pp. 124- 144 ,(1992) , 10.1007/3-540-55251-0_7
Stephen T. Hedetniemi, Thomas Victor Wimer, Linear algorithms on k-terminal graphs Clemson University. ,(1987)
Satoru Miyano, The Lexicographically First Maximal Subgraph Problems: P-Completeness and NC Algorithms international colloquium on automata languages and programming. ,vol. 22, pp. 425- 434 ,(1987) , 10.1007/BF02088292
A. Habel, Hyperedge Replacement: Grammars and Languages ,(1992)
Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, Detlef Seese, An Algebraic Theory of Graph Reduction international workshop on graph grammars and their application to computer science. pp. 70- 83 ,(1990) , 10.1007/BFB0017382
Stephan Heilbrunner, Lothar Schmitz, An efficient recognizer for the boolean closure of context-free languages Theoretical Computer Science. ,vol. 80, pp. 53- 75 ,(1991) , 10.1016/0304-3975(91)90205-G
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
Richard B. Borie, R. Gary Parker, Craig A. Tovey, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families Algorithmica. ,vol. 7, pp. 555- 581 ,(1992) , 10.1007/BF01758777
Jacobo Valdes, Robert E. Tarjan, Eugene L. Lawler, The Recognition of Series Parallel Digraphs SIAM Journal on Computing. ,vol. 11, pp. 298- 313 ,(1982) , 10.1137/0211023
K. Takamizawa, T. Nishizeki, N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs Journal of the ACM. ,vol. 29, pp. 623- 641 ,(1982) , 10.1145/322326.322328