{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:13Z","timestamp":1725663613486},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551218"},{"type":"electronic","value":"9783540467359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T04:47:30Z","timestamp":1330231650000},"page":"13-24","source":"Crossref","is-referenced-by-count":3,"title":["Monadic second-order evaluations on tree-decomposable graphs"],"prefix":"10.1007","author":[{"given":"B.","family":"Courcelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Mosbah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D.G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree, SIAM J. Alg. Disc. Meth., 8(1987), 277\u2013287.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"2_CR2","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski and D. Seese. An algebraic theory of graph reduction, Report 90\u201302, Bordeaux-1 University (1990)."},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/3-540-19488-6_105","volume":"317","author":"S. Arnborg","year":"1988","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Problems easy for tree decomposable graphs.(extended abstract), Proc. 15th ICALP. Springer Verlag, Lect. Notes in Comp. Sc. 317(1988) 38\u201351.","journal-title":"Proc. 15th ICALP. Springer Verlag, Lect. Notes in Comp. Sc."},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg, and A. Proskurowski. Characterization and recognition of partial 3-trees, SIAM J. Alg. Disc. Meth., 7(1986), 305\u2013314.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"M. Bauderon and B. Courcelle. Graph expressions and graph rewritings, Math. systems Theory 20(1987), 83\u2013127.","journal-title":"Math. systems Theory"},{"key":"2_CR6","unstructured":"H.L. Bodlaender. Complexity of path forming games, Report RUU-CS-89-29, Utrecht University (1989)."},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/3-540-19487-8_26","volume":"318","author":"H.L. Bodlaender","year":"1988","unstructured":"H.L. Bodlaender. Polynomial algorithms for chromatic index and graph isomorphism on partial k-trees, in Proc. 1st Scandinavian Workshop on Algorithmic Theory. Springer Verlag, Lect. Notes in Comp. Sc. 318(1988) 223\u2013232.","journal-title":"Springer Verlag, Lect. Notes in Comp. Sc."},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"J.A. Bern","year":"1987","unstructured":"J.A. Bern, E. Lawler and A. Wong. Linear time computation of optimal subgraphs of decomposable graphs, J. Algorithms 8(1987), 216\u2013235.","journal-title":"J. Algorithms"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation 85(1990), 12\u201375.","journal-title":"Information and Computation"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Graph rewriting: an algebraic and logic approach, in Handbook of Computer Science, Volume B, J. Van Leeuwen Ed., Elsevier (1990), 193\u2013242.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"2_CR11","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0304-3975(91)90387-H","volume":"80","author":"B. Courcelle","year":"1991","unstructured":"B. Courcelle. The monadic second-order logic of graphs V: On closing the gap between definability and recognizibility, Theoret. Compt. Sci. 80(1991) 153\u2013202.","journal-title":"Theoret. Compt. Sci."},{"key":"2_CR12","unstructured":"B. Courcelle, M. Mosbah. Monadic second-order evaluations on treedecomposable graphs, Report 90\u2013110, Bordeaux-1 University (1990)."},{"key":"2_CR13","unstructured":"P. Deransart, M. Jourdan, B. Lorho. Attribute grammars, Springer Verlag, Lect. Notes in Comp. Sc. 323(1988)."},{"key":"2_CR14","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability, W.H. Freeman and Company, San Francisco (1979)."},{"key":"2_CR15","unstructured":"A. Habel. Hyperedge Replacement Grammars and Languages, PhD. thesis, Bremen University (1989)."},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/3-540-50939-9_138","volume":"351","author":"A. Habel","year":"1989","unstructured":"A. Habel, H.J. Kreowski and W. Vogler. Decidable boundness problems for hyperedge replacement graph grammars, Springer Verlag, Lect. Notes in Comp. Sc. 351(1989) 275\u2013289.","journal-title":"Springer Verlag, Lect. Notes in Comp. Sc."},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D.S. Johnson","year":"1985","unstructured":"D.S. Johnson. The NP-completeness column: An ongoing guide (16th), J. algorithms 6(1985), 434\u2013451.","journal-title":"J. algorithms"},{"key":"2_CR18","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02088292","volume":"22","author":"S. Miyano","year":"1989","unstructured":"S. Miyano. The lexicographically first maximal subgraph problems: P-completeness and NC algorithms, Math. systems Theory 22(1989) 47\u201373.","journal-title":"Math. systems Theory"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. Valdes, E. Lawler and R. Tarjan. The recognition of series-parallel digraphs, SIAM J. Comput. 11(1982) 289\u2013313.","journal-title":"SIAM J. Comput."},{"key":"2_CR20","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki and N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs, J. Assoc. Comput. Mach 29(1982) 623\u2013641.","journal-title":"J. Assoc. Comput. Mach"},{"key":"2_CR21","unstructured":"T. Wimer. Linear algorithms on k-terminal graphs, PhD. thesis, Clemson University(1987)."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:57:38Z","timestamp":1605628658000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}