{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T07:51:50Z","timestamp":1725263510701},"reference-count":37,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1992]]},"DOI":"10.1051\/ita\/1992260302571","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T15:10:44Z","timestamp":1486048244000},"page":"257-286","source":"Crossref","is-referenced-by-count":108,"title":["The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues"],"prefix":"10.1051","volume":"26","author":[{"given":"B.","family":"Courcelle","sequence":"first","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"1. ARNBORG S., CORNEIL D. and PROSKUROWSKI A., Complexity of finding an embedding in a k-tree, S.I.A.M. J. Alg. Disc. Methods, 1987, 8, pp. 277-284.8811870611.05022","DOI":"10.1137\/0608024"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"2. ARNBORG S., COURCELLE B., PROSKUROWSKI A. and SEESE D., 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.14312740765.68062","DOI":"10.1007\/BFb0017382"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"3. ARNBORG S., LAGERGREN J. et SEESE D., Easy problems for tree decomposable graphs, J. Algorithms, 1991, 12, pp. 308-340.11054790734.68073","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"4. ARNBORG S. and PROSKUROWSKI A., Characterization and recognition of partial 3-trees, S.I.A.M. J. Alg. Disc. Meth., 1986, 7, pp. 305-314.8306490597.05027","DOI":"10.1137\/0607033"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"5. ARNBORG S. PROSKUROWSKI A. and CORNEIL D., Forbidden minors characterization of partial 3-trees, Discrete Math., 1990, 80, pp. 1-19.10459200701.05016","DOI":"10.1016\/0012-365X(90)90292-P"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"6. BAUDERON M., Infinite hypergraphs, I, Basic proporties, Theoret. Comput. Sci., 1991, 82, pp. 177-214.11127680758.05069","DOI":"10.1016\/0304-3975(91)90222-N"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"7. BAUDERON M. and COURCELLE B., Graph expressions and graph rewritings, Math. System Theory, 1987, 29, pp. 83-127.9207700641.68115","DOI":"10.1007\/BF01692060"},{"key":"R8","unstructured":"8. BODLAENDER H., Classes of graphs w\u00efth bounded tree-width, Report RUU-CS-86-22, University of Utrecht, The Netherlands, 1986."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"9. BODLAENDER H., 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.10193740651.68079","DOI":"10.1007\/3-540-19487-8_26"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"10. BODLAENDER H., Dynamic programming on graphs with bounded tree width, Proceedings of ICALP'88, Tampere, Finland, L.N.C.S, 317, 1988, pp. 105-118.10236300649.68039","DOI":"10.1007\/3-540-19488-6_110"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"11. BODLAENDER H., Improved self-reduction algorithms for graphs with bounded tree-width, Proceedings of WG'89, Lecture Notes in Comput. Sci., 1990, 411, pp. 232-244.10639460768.68033","DOI":"10.1007\/3-540-52292-1_17"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"12. COURCELLE B., An axiomatic definition of eontext-free rewriting and its application to NLC graph grammars, Theoret. Comput. Sci., 1987, 55, pp. 141-181.9324450644.68095","DOI":"10.1016\/0304-3975(87)90102-2"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"13. COURCELLE B., The monadic second-order theory of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 1990, 85, pp. 12-75.10426490722.03008","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"14. COURCELLE B., The monadic second-order logie of graphs II: Infinite graphs of bounded with, Math. Systems Theory, 1989, 21, pp. 187-221.9871500694.68043","DOI":"10.1007\/BF02088013"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"15. COURCELLE B., The monadic second-order logic of graphs IV, Definability results for equational graphs, Ann. Pure Appl. Logic, 1990, 49, pp. 193-255.10772590731.03006","DOI":"10.1016\/0168-0072(90)90027-Y"},{"key":"R16","unstructured":"16. COURCELLE B., 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).0809.03005"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"17. COURCELLE B., Graph rewriting: an algebraic and logic approach, in Handbook of Theoretical computer Science, vol. B, J. VAN LEEUWEN Ed. 1990, Elsevier, pp. 193-242.0900.68282","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"R18","unstructured":"18. COURCELLE B. and MOSBAH M., Monadic second-order evaluations on tree-decomposable graphs, Rapport 90-110, Bordeaux-I, University, 1990. Theor. Comput. Sci., (to appear).0789.68083"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"19. FELLOWS M. and LANGSTON M., On Search, decision and the efficiency of polynomial-time algorithms, A.C.M. Symp. on Theory of Computing 1989, pp. 501-512.","DOI":"10.1145\/73007.73055"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"20. FELLOWS M. and LANGSTON M., 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.","DOI":"10.1109\/SFCS.1989.63528"},{"key":"R21","unstructured":"21. HABEL A., Hyperedge replacement: grammars and languages, Doctoral dissertation, University of Bremen 1989."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"22. HABEL A. and KREOWSKI H. J., May we introduce to you: hyperedge replacement, L.N.C.S., 1987, 291, pp. 15-26.0643.68106","DOI":"10.1007\/3-540-18771-5_41"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"23. LAUTEMANN C., Efficient algorithms on context-free graph languages, ICALP'88, Tampere, Finland, L.N.C.S., 1987, 317, pp. 362-378.0649.68075","DOI":"10.1007\/3-540-19488-6_128"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"24. LEUNG J., WITTHOF J. and VORNBERGER O., On some variations on the bandwidth minization problem, S.I.A.M. J. Comput., 1984, 13, pp. 650-667.0545.68058","DOI":"10.1137\/0213040"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"25. ROBERTSON N. and SEYMOUR P., Some new results on the well-quasi-ordering of graphs, Ann. Discrete Math., 1984, 23, pp. 343-354.0556.05058","DOI":"10.1016\/S0304-0208(08)73830-1"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"26. ROBERTSON N. and SEYMOUR P., Graph Minors IV, Tree-width and well quasiordering, J. Combin. Theory, Ser. B. 48, 1990, pp. 227-254.10467570719.05032","DOI":"10.1016\/0095-8956(90)90120-O"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"27. ROBERTSON N. and SEYMOUR P., Graph Minors V, excluding a planar graph, J. Combin. Theory, Ser. B., 1986, 41, pp. 92-114.8546060598.05055","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"R28","unstructured":"28. ROBERTSON N. and SEYMOUR P., Graph Minors X, Obstructions to tree-decomposition, Revised version, Feb. 1988."},{"key":"R29","unstructured":"29. ROBERTSON N. and SEYMOUR P., Graph Minors XIII, The disjoint paths problem, Preprint, September 1986.0823.050381309358"},{"key":"R30","unstructured":"30. ROBERTSON N. and SEYMOUR P., Graph Minors XV, Wagner's conjecture, Revised version, March 1988."},{"key":"R31","unstructured":"31. SEESE D., Ein Unentscheidbarkeitskreiterium, Wiss. Z. der Humbold Univ. Zu Berlin Math. Natur. Wiss., R24, 1975, pp. 772-780.0331.02026"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"32. SEESE D., The structure of the models of decidable monadic theories of graphs. Ann. Pure and Appl. Logic, 1991, 53, pp. 169-195.11148480733.03026","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"33. VAN LEEUWEN J., Graph algorithms, Handbook of Theoretical Computer Science, volume A\", J. VAN LEEUWEN Ed., 1990, Elsevier, pp. 523-631.11271760900.68258","DOI":"10.1016\/B978-0-444-88071-0.50015-1"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"34. VOGLER W., 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.14312960769.68078","DOI":"10.1007\/BFb0017421"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"35. WAGNER K., Ueber eine Eigenshaft der ebenen Komplexe, Math. Ann., 1937, 114, pp. 570-590.15993515131580017.19005","DOI":"10.1007\/BF01594196"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"36. WALD J. and COLBOURN C., Steiner trees, partial 2-trees, and IFI networks, Networks, 1983,13, pp. 159-167.7064890529.68036","DOI":"10.1002\/net.3230130202"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"37. LAGERGREN J. and ARNBORG S., Finding minimal forbiden minors using a finite congruence, L.N.C.S. 510, 1991, pp. 532-543.11299330764.68122","DOI":"10.1007\/3-540-54233-7_161"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1992260302571\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T05:59:54Z","timestamp":1568786394000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1992260302571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"references-count":37,"journal-issue":{"issue":"3"},"alternative-id":["ita1992260302571"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1992260302571","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}