{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:12Z","timestamp":1761611172489},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540642305"},{"type":"electronic","value":"9783540697053"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"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":[[1998]]},"DOI":"10.1007\/bfb0028596","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T02:33:39Z","timestamp":1132626819000},"page":"618-628","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width"],"prefix":"10.1007","author":[{"given":"Denis","family":"Lapoire","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"54_CR1","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:83\u2013127, 1987.","journal-title":"Math. Systems Theory"},{"key":"54_CR2","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"5","author":"J. B\u00fcchi","year":"1960","unstructured":"J. B\u00fcchi. Weak second order logic and finite automata. S. Math. Logik Grundlagen Math., 5:66\u201392, 1960.","journal-title":"S. Math. Logik Grundlagen Math."},{"key":"54_CR3","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. Inf. and Comp., 85:12\u201375, 1990.","journal-title":"Inf. and Comp."},{"key":"54_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0168-0072(90)90027-Y","volume":"49","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs, IV: Definability properties of equational graphs. Annals of Pure and Applied Logic, 49:193\u2013255, 1990.","journal-title":"Annals of Pure and Applied Logic"},{"key":"54_CR5","doi-asserted-by":"publisher","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 recognizability. Theoret. Comput. Sci., 80:153\u2013202, 1991.","journal-title":"Theoret. Comput. Sci."},{"key":"54_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"B. Courcelle","year":"1994","unstructured":"B. Courcelle. Monadic second order definable graph transductions: A survey. Theoret. Comput. Sci., 126:53\u201375, 1994.","journal-title":"Theoret. Comput. Sci."},{"key":"54_CR7","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"J. Doner. Tree acceptors and some of their applications. J. Comput. System Sci., 4:406\u2013451, 1970.","journal-title":"J. Comput. System Sci."},{"key":"54_CR8","first-page":"15","volume":"291","author":"A. Habel","year":"1987","unstructured":"A. Habel and H.-J. Kreowski. May we introduce to you, hyperedge replacement. LNCS 291, pages 15\u201326, 1987.","journal-title":"LNCS"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"V. Kabanets. Recognizability equals definability for partial k-trees. In ICALP '97, pages 805\u2013815, 1997.","DOI":"10.1007\/3-540-63165-8_233"},{"key":"54_CR10","doi-asserted-by":"crossref","unstructured":"D. Kaller. Definability equals recognizability of partial 3-trees. In (WG '96), editor, Workshop on Graph-Theoretic Concepts in Computer Science, pages 239\u2013253, 1996.","DOI":"10.1007\/3-540-62559-3_20"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0019-9958(67)90353-1","volume":"11","author":"J. Mezei","year":"1967","unstructured":"J. Mezei and J. Wright. Algebraic automata and context-free sets. Inform. and Control, 11:3\u201329, 1967.","journal-title":"Inform. and Control"},{"key":"54_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P. D. Seymour. Graph minors. III. planar tree-width. J. Combin. Theory Ser. B, 36:49\u201364, 1984.","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Lecture Notes in Computer Science","STACS 98"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T17:21:15Z","timestamp":1558286475000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642305","9783540697053"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0028596","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}