Monadic second-order evaluations on tree-decomposable graphs. (English) Zbl 0789.68083

Courcelle, B.; Mosbah, M.

Theor. Comput. Sci. 109, No. 1-2, 49-82 (1993).

Summary: Every graph generated by a hyperedge replacement graph-grammar can be represented by a tree, namely the derivation tree of the derivation sequence that produced it. Certain functions on graphs can be computed recursively on the derivation trees of these graphs. By using monadic second-order logic and semiring homomorphisms, we describe in a single formalism a large class of such functions. Polynomial and even linear algorithms can be constructed for some of these functions. We unify similar results obtained by K. Takamizawa, T. Nishizeki and N. Saito [J. Assoc. Comput. Mach. 29, 623-641 (1982; Zbl 0485.68055)], M. W. Bern, E. L. Lawler and A. L. Wong [J. Algorithms 8, 216-235 (1987; Zbl 0618.68058)], S. Arnborg, J. Lagergren and D.Seese [J. Algorithms 12, 308-340 (1991; Zbl 0734.68073)] and A. Hable, H. J. Kreowski and W. Vogler [Lect. Notes Comput. Sci. 351, 275-289 (1989)].

MSC:

68Q42	Grammars and rewriting systems
68R10	Graph theory (including graph drawing) in computer science
03B15	Higher-order logic; type theory (MSC2010)
68Q25	Analysis of algorithms and problem complexity

Keywords:

hyperedge replacement graph-grammar; derivation tree; functions on graphs; monadic second-order logic; semiring homomorphisms; linear algorithms

Citations:

Zbl 0485.68055; Zbl 0618.68058; Zbl 0734.68073

References:

[1]	Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8, 277-287 (1987) · Zbl 0611.05022
[2]	Arnborg, S.; Courcelle, B.; Proskurowski, A.; Seese, D., An algebraic theory of graph reduction, (Report 90-92 (1990), Bordeaux-1 University). (Lecture Notes in Computer Science, Vol. 532 (1987), Springer: Springer Berlin), 70-83, Short version in · Zbl 0765.68062
[3]	Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree decomposable graphs, J. Algorithms, 12, 308-340 (1991) · Zbl 0734.68073
[4]	Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 305-314 (1986) · Zbl 0597.05027
[5]	Bauderon, M.; Courcelle, B., Graph rewriting and graph expressions, Math. Systems Theory, 20, 83-127 (1987) · Zbl 0641.68115
[6]	Bern, J. A.; Lawler, E.; Wong, A., Linear time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 216-235 (1987) · Zbl 0618.68058
[7]	Bodlaender, H. L., Dynamic programming algorithms on graphs with bounded tree-width, (Proc. 15th ICALP. Proc. 15th ICALP, Lecture Notes in Computer Science, Vol. 317 (1988), Springer: Springer Berlin), 223-232
[8]	Bodlaender, H. L., Improved self-reduction algorithms for graphs with bounded tree-width, (Tech. Report RUU-CS-88-29 (1988), University of Utrecht) · Zbl 0684.68047
[9]	Bodlaender, H. L., Complexity of path forming games, (RUU-CS-89-29 (1989), Utrecht University) · Zbl 0776.90100
[10]	Bodlaender, H. L., Polynomial algorithms for graph isomorphism and chromatic index on partial \(k\)-trees, J. Algorithms, 11, 631-643 (1990) · Zbl 0716.68042
[11]	Bodlaender, H. L.; Kloks, T., Better algorithms for path-width and tree-width of graphs, (ICALP ’91. ICALP ’91, Lecture Notes in Computer Science, Vol. 510 (1991), Springer: Springer Berlin)
[13]	Courcelle, B., Graph rewriting: an algebraic and logic approach, (van Leeuwen, J., Handbook of Computer Science, Vol. B (1990), Elsevier: Elsevier Amsterdam), 193-242 · Zbl 0900.68282
[14]	Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. and Comput., 85, 12-75 (1990) · Zbl 0722.03008
[15]	Courcelle, B., The monadic second-order logic of graphs V: on closing the gap between definability and recognizability, Theoret. Comput. Sci., 80, 53-202 (1991) · Zbl 0754.68065
[16]	Courcelle, B., Monadic second-order definable transductions, CAAP’92. CAAP’92, Rennes, February 24-28. CAAP’92. CAAP’92, Rennes, February 24-28, Lecture Notes in Computer Science (1992), to appear
[17]	Deransart, P.; Jourdan, M.; Lorho, B., Attribute grammars, (Lecture Notes in Computer Science, Vol. 323 (1988), Springer: Springer Berlin) · Zbl 0647.68073
[18]	Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039
[19]	Habel, A., Hyperedge replacement: grammars and languages, (Ph.D. Thesis (1989), University of Bremen) · Zbl 0787.68066
[20]	Habel, A.; Kreowski, H. J.; Vogler, W., Decidable boundness problems for hyperedge replacement graph grammars, (Lecture Notes in Computer Science, Vol. 351 (1989), Springer: Springer Berlin), 275-289
[21]	Hohberg, W.; Reischuk, R., A framework to algorithms for optimization problems on graphs, (Technical Report (1990), Technische Hochschule Darmstadt: Technische Hochschule Darmstadt Germany)
[22]	Johnson, D. S., The NP-completeness column: an ongoing guide (16th), J. Algorithms, 6, 434-451 (1985) · Zbl 0608.68032
[23]	Lagergren, J., Efficient parallel algorithms for tree-decomposition and related problems, Proc. IEEE Symp. on FOCS, 173-182 (1990)
[24]	Miyano, S., The lexicographically first maximal subgraph problems: P-completeness and NC algorithms, Math. Systems Theory, 22, 47-73 (1989) · Zbl 0679.68090
[25]	Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. Assoc. Comput. Mach., 29, 623-641 (1982) · Zbl 0485.68055
[26]	Thatcher, J. W.; Wright, J. B., Generalized finite automata theory with an application to a decision problem in second-order logic, Math. Systems Theory, 2, 57-81 (1968) · Zbl 0157.02201
[27]	Valdes, J.; Lawler, E.; Tarjan, R., The recognition of series-parallel digraphs, SIAM J. Comput., 11, 289-313 (1982) · Zbl 0478.68065
[28]	Wimer, T., Linear algorithms on k-terminal graphs, (Ph.D. Thesis (1987), Clemson University) · Zbl 0669.05050