Monadic second-order evaluations on tree-decomposable graphs

Theoretical Computer Science - Tập 109 - Trang 49-82 - 1993
B. Courcelle1, M. Mosbah1
1Université Bordeaux-I, Laboratoire d'Informatique, 351, cours de la Libération, 33405 Talence, France

Tài liệu tham khảo

Arnborg, 1987, Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 277, 10.1137/0608024 Arnborg, 1990, An algebraic theory of graph reduction Arnborg, 1991, Easy problems for tree decomposable graphs, J. Algorithms, 12, 308, 10.1016/0196-6774(91)90006-K Arnborg, 1986, Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 305, 10.1137/0607033 Bauderon, 1987, Graph rewriting and graph expressions, Math. Systems Theory, 20, 83, 10.1007/BF01692060 Bern, 1987, Linear time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 216, 10.1016/0196-6774(87)90039-3 Bodlaender, 1988, Dynamic programming algorithms on graphs with bounded tree-width, Vol. 317, 223 Bodlaender, 1988, Improved self-reduction algorithms for graphs with bounded tree-width Bodlaender, 1989, Complexity of path forming games Bodlaender, 1990, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11, 631, 10.1016/0196-6774(90)90013-5 Bodlaender, 1991, Better algorithms for path-width and tree-width of graphs, Vol. 510 R.B. Borie, R.G. Parker and C.A. Tovey, Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, to appear. Courcelle, 1990, Graph rewriting: an algebraic and logic approach, Vol. B, 193 Courcelle, 1990, The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. and Comput., 85, 12, 10.1016/0890-5401(90)90043-H Courcelle, 1991, The monadic second-order logic of graphs V: on closing the gap between definability and recognizability, Theoret. Comput. Sci., 80, 53, 10.1016/0304-3975(91)90387-H Courcelle, 1992, Monadic second-order definable transductions, Lecture Notes in Computer Science, 10.1007/3-540-55251-0_7 Deransart, 1988, Attribute grammars, Vol. 323 Garey, 1979 Habel, 1989, Hyperedge replacement: grammars and languages Habel, 1989, Decidable boundness problems for hyperedge replacement graph grammars, Vol. 351, 275 Hohberg, 1990, A framework to algorithms for optimization problems on graphs Johnson, 1985, The NP-completeness column: an ongoing guide (16th), J. Algorithms, 6, 434, 10.1016/0196-6774(85)90012-4 Lagergren, 1990, Efficient parallel algorithms for tree-decomposition and related problems, Proc. IEEE Symp. on FOCS, 173 Miyano, 1989, The lexicographically first maximal subgraph problems: P-completeness and NC algorithms, Math. Systems Theory, 22, 47, 10.1007/BF02088292 Takamizawa, 1982, Linear-time computability of combinatorial problems on series–parallel graphs, J. Assoc. Comput. Mach., 29, 623, 10.1145/322326.322328 Thatcher, 1968, Generalized finite automata theory with an application to a decision problem in second-order logic, Math. Systems Theory, 2, 57, 10.1007/BF01691346 Valdes, 1982, The recognition of series-parallel digraphs, SIAM J. Comput., 11, 289, 10.1137/0211023 Wimer, 1987, Linear algorithms on k-terminal graphs