{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:13Z","timestamp":1759637713315},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540507284"},{"type":"electronic","value":"9783540460763"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-50728-0_34","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:33:08Z","timestamp":1330183988000},"page":"30-53","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["The monadic second-order logic of graphs : Definable sets of finite graphs"],"prefix":"10.1007","author":[{"given":"Bruno","family":"Courcelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"ARNBORG S., CORNEIL D., PROSKUROWSKI A., Complexity of finding an embedding in a k-tree. SIAM J. of Alg. and Discr. Methods 8 (1987) 277\u2013284","journal-title":"SIAM J. of Alg. and Discr. Methods"},{"key":"3_CR2","unstructured":"ARNBORG S., PROSKUROWSKI A., Linear time algorithms for port TRITA NA 8404 (1984), Stockolm."},{"key":"3_CR3","unstructured":"ARNBORG S., LAGERGREN J., SEESE D., Which problems are easy for tree decomposable graphs ? Preprint, Nov. 1987, and Proc. of ICALP' 88, Tampere, Lec. Notes in Comput. Sci. 317, pp. 38\u201351."},{"key":"3_CR4","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"BAUDERON M., COURCELLE B., Graph expressions and graph rewritings, Math Systems Theory 20 (1987) 83\u2013127","journal-title":"Math Systems Theory"},{"key":"3_CR5","unstructured":"BODLAENDER H., Dynamic programming on graphs with bounded tree-width, Proc. ICALP' 88, Lec. Notes Comp. Sci. 317, pp. 105\u2013132."},{"key":"3_CR6","unstructured":"BODLAENDER H., NC-algorithms for graphs with small tree-width, this volume."},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(86)90050-2","volume":"42","author":"B. Courcelle","year":"1986","unstructured":"COURCELLE B., Equivalences and transformations of regular systems. Applications to recursive program schemes and grammars, Theor. Comp. Sci. 42 (1986) 1\u2013122.","journal-title":"Theor. Comp. Sci."},{"key":"3_CR8","unstructured":"COURCELLE B., Recognizability and second order defi nability for sets of finite graphs, Report I-8634, (revised version: The monadic second order logic of graphs, I: Recognizable sets of finite graphs, to appear)."},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","volume":"55","author":"B. Courcelle","year":"1987","unstructured":"COURCELLE B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoret. Comput. Sci. 55 (1987) 141\u2013181.","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR10","first-page":"112","volume":"291","author":"B. Courcelle","year":"1987","unstructured":"COURCELLE B., A representation of graphs by algebraic expressions and its use for graph rewriting systems, Proceedings of the 3rd international workshop on graph grammars, Warrenton, Virginia, 1986 in Lec. Notes Comput. Science vol. 291, 1987 pp. 112\u2013133","journal-title":"Science"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"COURCELLE B., On context-free sets of graphs and their monadic 2nd-order theory, same volume as [10], pp. 133\u2013146.","DOI":"10.1007\/3-540-18771-5_50"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"COURCELLE B., On recognizable sets and tree-automata Report 8736, Proc. of the Conference on the resolution of equations in algebraic structures (CREAS), M. Nivat and H. Ait-Kaci eds., Academic Press, to appear in 1989.","DOI":"10.1016\/B978-0-12-046370-1.50009-7"},{"key":"3_CR13","unstructured":"COURCELLE B., On the use of context-free graph grammars for analyzing recursive definitions, Second French-Japanese Seminar, L. Kott ed., North-Holland, to appear in 1988."},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"DONER J., Tree acceptors and some of their applications J. Comput. System Sci. 4 (1970) 406\u2013451.","journal-title":"J. Comput. System Sci."},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. Johnson","year":"1985","unstructured":"JOHNSON D., The NP-completeness column: an ongoing guide, (16th), J. of Algorithms 6 (1985) 434\u2013451.","journal-title":"J. of Algorithms"},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(87)90043-5","volume":"8","author":"D. Johnson","year":"1987","unstructured":"JOHNSON D., The NP-completeness column: An ongoing guide (19 th), J. of Algorithms 8 (1987) 285\u2013303.","journal-title":"J. of Algorithms"},{"key":"3_CR17","unstructured":"HABEL A., Graph-theoretic properties compatible with graph derivations, this volume."},{"key":"3_CR18","first-page":"207","volume":"247","author":"A. Habel","year":"1987","unstructured":"HABEL A., KREOWSKI H. J., Some structural aspects of hyperedge languages generated by hyperedge replacements, preprint Oct. 85,and L.N.C.S. vol. 247, 1987, pp. 207\u2013219.","journal-title":"L.N.C.S."},{"key":"3_CR19","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/BFb0026094","volume":"299","author":"C. Lautemann","year":"1988","unstructured":"LAUTEMANN C., Decomposition trees: structured graph repre sentations and efficient algorithms, Lec. Notes Comp. Sci. 299, pp. 28\u201339, 1988.","journal-title":"Lec. Notes Comp. Sci."},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-19488-6_128","volume":"317","author":"C. Lautemann","year":"1988","unstructured":"LAUTEMANN C., Efficient algorithms on context-free graph languages, Proc. ICALP' 88, Lec. Notes Comp. Sci. 317 pp. 362\u2013378, 1988.","journal-title":"Lec. Notes Comp. Sci."},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"LENGAUER T., WANKE E., Efficient analysis of graph properties on context-free graph languages, Proc. ICALP 1988, Lec. Notes Comp. Sci. 317, pp. 379\u2013393.","DOI":"10.1007\/3-540-19488-6_129"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0019-9958(67)90353-1","volume":"11","author":"J. Mezei","year":"1967","unstructured":"MEZEI J., WRIGHT J., Algebraic automata and context-free sets, Information and Control 11 (1967) 3\u201329.","journal-title":"Information and Control"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"MONIEN B., SUDBOROUGH H., Bandwidth constrained NP complete problems, 13th ACM Symp. on Theory of computation, 1981, pp. 207\u2013217.","DOI":"10.1145\/800076.802474"},{"key":"3_CR24","first-page":"343","volume":"23","author":"N. Robertson","year":"1984","unstructured":"ROBERTSON N., SEYMOUR P., Some new results on the well quasi-ordering of graphs, Annals of Discrete Mathematics 23 (1984), 343\u2013354, Elsevier Pub.","journal-title":"Annals of Discrete Mathematics"},{"key":"3_CR25","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"ROBERTSON N., SEYMOUR P., Graph minors V, Excluding a planar graph, J. Combinatorial Theory Ser. B, 41 (1986) 92\u2013114.","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"3_CR26","unstructured":"ROBERTSON N., SEYMOUR P., Graph minors XVI, Wagner's conjecture, in preparation, 1988."},{"key":"3_CR27","unstructured":"SEESE D., The structure of the models of decidable monadic theories of graphs, 1987, submitted for publication."},{"key":"3_CR28","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. Thatcher","year":"1970","unstructured":"THATCHER J., WRIGHT J., Generalized finite automata theory, Math. Systems Theory 2 (1970) 57\u201381.","journal-title":"Math. Systems Theory"},{"key":"3_CR29","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"WAGNER K., Uber eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937) 570\u2013590.","journal-title":"Math. Ann."},{"key":"3_CR30","unstructured":"WIMER T., HEDETNIEMI S., LASKAR R., A methodology for constructing linear graph algorithms, DCS, Clemson Univ, 1985"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50728-0_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:13:32Z","timestamp":1558253612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50728-0_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540507284","9783540460763"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-50728-0_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}