×

zbMATH — the first resource for mathematics

The monadic second-order logic of graphs. III: Tree-decompositions, minors and complexity issues. (English) Zbl 0754.03006
The paper continues the study of graphs, hypergraphs and sets thereof using methods of formal language theory, universal algebra and logic, a study initiated by Bauderon and the author [see Zbl 0722.03008, Zbl 0694.68043 and Zbl 0731.03006]. He relates the tree-decompositions of hypergraphs introduced by Robertson and Seymour to the finite and infinite algebraic expressions introduced in the earlier parts. The minor inclusion is expressed in monadic second-order logic, and the grammatical characterizations of certain sets of graphs defined by excluded minors are obtained. The author shows how tree-decompositions can be used to construct quadratic algorithms deciding monadic second-order properties on hypergraphs of bounded tree-width.
Reviewer: Li Xiang (Guiyang)

MSC:
03B15 Higher-order logic; type theory (MSC2010)
68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
03B25 Decidability of theories and sets of sentences
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] 1. S. ARNBORG, D. CORNEIL and A. PROSKUROWSKI, Complexity of finding an embedding in a k-tree, S.I.A.M. J. Alg. Disc. Methods, 1987, 8, pp. 277-284. Zbl0611.05022 MR881187 · Zbl 0611.05022
[2] 2. S. ARNBORG, B. COURCELLE, A. PROSKUROWSKI and D. SEESE, An algebraic theory of graph reduction, Report 90-02, Bordeaux-I University, 1990. Short version in L.N.C.S., 532, 1991, pp. 70-83. Zbl0765.68062 MR1431274 · Zbl 0765.68062
[3] 3. S. ARNBORG, J. LAGERGREN et D. SEESE, Easy problems for tree decomposable graphs, J. Algorithms, 1991, 12, pp. 308-340. Zbl0734.68073 MR1105479 · Zbl 0734.68073
[4] 4. S. ARNBORG and A. PROSKUROWSKI, Characterization and recognition of partial 3-trees, S.I.A.M. J. Alg. Disc. Meth., 1986, 7, pp. 305-314. Zbl0597.05027 MR830649 · Zbl 0597.05027
[5] 5. S. ARNBORG A. PROSKUROWSKI and D. CORNEIL, Forbidden minors characterization of partial 3-trees, Discrete Math., 1990, 80, pp. 1-19. Zbl0701.05016 MR1045920 · Zbl 0701.05016
[6] 6. M. BAUDERON, Infinite hypergraphs, I, Basic proporties, Theoret. Comput. Sci., 1991, 82, pp. 177-214. Zbl0758.05069 MR1112768 · Zbl 0758.05069
[7] 7. M. BAUDERON and B. COURCELLE, Graph expressions and graph rewritings, Math. System Theory, 1987, 29, pp. 83-127. Zbl0641.68115 MR920770 · Zbl 0641.68115
[8] 8. H. BODLAENDER, Classes of graphs wïth bounded tree-width, Report RUU-CS-86-22, University of Utrecht, The Netherlands, 1986.
[9] 9. H. BODLAENDER, Polynomial algorithms for Chromatic Index and Graph Isomorphism on partial k-trees, Proc. First Scandinavian Workshop on Algorithm theory, 1988, Lecture Notes in Comput. Sci., 318, pp. 223-232. Zbl0651.68079 MR1019374 · Zbl 0651.68079
[10] 10. H. BODLAENDER, Dynamic programming on graphs with bounded tree width, Proceedings of ICALP’88, Tampere, Finland, L.N.C.S, 317, 1988, pp. 105-118. Zbl0649.68039 MR1023630 · Zbl 0649.68039
[11] 11. H. BODLAENDER, Improved self-reduction algorithms for graphs with bounded tree-width, Proceedings of WG’89, Lecture Notes in Comput. Sci., 1990, 411, pp. 232-244. Zbl0768.68033 MR1063946 · Zbl 0768.68033
[12] 12. B. COURCELLE, An axiomatic definition of eontext-free rewriting and its application to NLC graph grammars, Theoret. Comput. Sci., 1987, 55, pp. 141-181. Zbl0644.68095 MR932445 · Zbl 0644.68095
[13] 13. B. COURCELLE, The monadic second-order theory of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 1990, 85, pp. 12-75. Zbl0722.03008 MR1042649 · Zbl 0722.03008
[14] 14. B. COURCELLE, The monadic second-order logie of graphs II: Infinite graphs of bounded with, Math. Systems Theory, 1989, 21, pp. 187-221. Zbl0694.68043 MR987150 · Zbl 0694.68043
[15] 15. B. COURCELLE, The monadic second-order logic of graphs IV, Definability results for equational graphs, Ann. Pure Appl. Logic, 1990, 49, pp. 193-255. Zbl0731.03006 MR1077259 · Zbl 0731.03006
[16] 16. B. COURCELLE, The monadic second-order logic of graphs VI: On several representations of graphs by logical structures, Research report 89-99, Bordeaux I-University. Discrete Appl. Math. (in press). (See also Logic in Comput. Sci., 1990. Philadelphia). Zbl0809.03005 · Zbl 0809.03005
[17] 17. B. COURCELLE, Graph rewriting: an algebraic and logic approach, in Handbook of Theoretical computer Science, vol. B, J. VAN LEEUWEN Ed. 1990, Elsevier, pp. 193-242. Zbl0900.68282 · Zbl 0900.68282
[18] 18. B. COURCELLE and M. MOSBAH, Monadic second-order evaluations on tree-decomposable graphs, Rapport 90-110, Bordeaux-I, University, 1990. Theor. Comput. Sci., (to appear). Zbl0789.68083 · Zbl 0789.68083
[19] 19. M. FELLOWS and M. LANGSTON, On Search, decision and the efficiency of polynomial-time algorithms, A.C.M. Symp. on Theory of Computing 1989, pp. 501-512.
[20] 20. M. FELLOWS and M. LANGSTON, An analogue of the Myhill-Nerode Theorem and its use in computing finite-basis characterization, 30th Annual I.E.E.E. Symp. on Foundations of Computer Science, 1989, pp. 520-525.
[21] 21. A. HABEL, Hyperedge replacement: grammars and languages, Doctoral dissertation, University of Bremen 1989.
[22] 22. A. HABEL and H. J. KREOWSKI, May we introduce to you: hyperedge replacement, L.N.C.S., 1987, 291, pp. 15-26. Zbl0643.68106 · Zbl 0643.68106
[23] 23. C. LAUTEMANN, Efficient algorithms on context-free graph languages, ICALP’88, Tampere, Finland, L.N.C.S., 1987, 317, pp. 362-378. Zbl0649.68075 · Zbl 0649.68075
[24] 24. J. LEUNG, J. WITTHOF and O. VORNBERGER, On some variations on the bandwidth minization problem, S.I.A.M. J. Comput., 1984, 13, pp. 650-667. Zbl0545.68058 · Zbl 0545.68058
[25] 25. N. ROBERTSON and P. SEYMOUR, Some new results on the well-quasi-ordering of graphs, Ann. Discrete Math., 1984, 23, pp. 343-354. Zbl0556.05058 · Zbl 0556.05058
[26] 26. N. ROBERTSON and P. SEYMOUR, Graph Minors IV, Tree-width and well quasiordering, J. Combin. Theory, Ser. B. 48, 1990, pp. 227-254. Zbl0719.05032 MR1046757 · Zbl 0719.05032
[27] 27. N. ROBERTSON and P. SEYMOUR, Graph Minors V, excluding a planar graph, J. Combin. Theory, Ser. B., 1986, 41, pp. 92-114. Zbl0598.05055 MR854606 · Zbl 0598.05055
[28] 28. N. ROBERTSON and P. SEYMOUR, Graph Minors X, Obstructions to tree-decomposition, Revised version, Feb. 1988.
[29] 29. N. ROBERTSON and P. SEYMOUR, Graph Minors XIII, The disjoint paths problem, Preprint, September 1986. MR1309358 · Zbl 0823.05038
[30] 30. N. ROBERTSON and P. SEYMOUR, Graph Minors XV, Wagner’s conjecture, Revised version, March 1988.
[31] 31. D. SEESE, Ein Unentscheidbarkeitskreiterium, Wiss. Z. der Humbold Univ. Zu Berlin Math. Natur. Wiss., R24, 1975, pp. 772-780. Zbl0331.02026 · Zbl 0331.02026
[32] 32. D. SEESE, The structure of the models of decidable monadic theories of graphs. Ann. Pure and Appl. Logic, 1991, 53, pp. 169-195. Zbl0733.03026 MR1114848 · Zbl 0733.03026
[33] 33. J. VAN LEEUWEN, Graph algorithms, Handbook of Theoretical Computer Science, volume A”, J. VAN LEEUWEN Ed., 1990, Elsevier, pp. 523-631. Zbl0900.68258 MR1127176 · Zbl 0900.68258
[34] 34. W. VOGLER, Recognizing edge replacement graphs languages in cubic time, Proceedings of the 4th Int. Workshop on Graph Grammars, Bremen 1990, L.N.C.S., 532, 1991, pp. 676-687. Zbl0769.68078 MR1431296 · Zbl 0769.68078
[35] 35. K. WAGNER, Ueber eine Eigenshaft der ebenen Komplexe, Math. Ann., 1937, 114, pp. 570-590. Zbl0017.19005 MR1513158 · Zbl 0017.19005
[36] 36. J. WALD and C. COLBOURN, Steiner trees, partial 2-trees, and IFI networks, Networks, 1983,13, pp. 159-167. Zbl0529.68036 MR706489 · Zbl 0529.68036
[37] 37. J. LAGERGREN and S. ARNBORG, Finding minimal forbiden minors using a finite congruence, L.N.C.S. 510, 1991, pp. 532-543. Zbl0764.68122 MR1129933 · Zbl 0764.68122
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.