{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:13Z","timestamp":1725664693180},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540630456"},{"type":"electronic","value":"9783540690658"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"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":[[1997]]},"DOI":"10.1007\/3-540-63045-7_6","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:00:50Z","timestamp":1330297250000},"page":"53-55","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finite model theory, universal algebra and graph grammars"],"prefix":"10.1007","author":[{"given":"Bruno","family":"Courcelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,25]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, D. Seese. Easy problems for tree decomposable graphs. J. of Algorithms 12:308\u2013340, 1991.","journal-title":"J. of Algorithms"},{"key":"6_CR2","doi-asserted-by":"crossref","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:12\u201375, 1990","journal-title":"Information and Computation"},{"key":"6_CR3","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 beween definability and recognizability. Theoret. Comput. Sci. 80:153\u2013202, 1991","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","volume":"54","author":"B. Courcelle","year":"1994","unstructured":"B. Courcelle. The monadic second-order logic of graphs VI: On several representations of graphs by relational structures Discrete Applied Mathematics 54:117\u2013149, 1994","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0304-3975(95)00083-6","volume":"160","author":"B. Courcelle","year":"1996","unstructured":"B. Courcelle. The monadic second order logic of graphs X: Linear orders. Theoret. Comput. Sci. 160:87\u2013143, 1996.","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(95)00145-X","volume":"163","author":"B. Courcelle","year":"1996","unstructured":"B. Courcelle. Basic notions of universal algebra; applications to formal language theory and graph grammars. Theoret. Comput. Sci. 163:1\u201354, 1996","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"B. Courcelle. The expression of graph properties and graph transformations in monadic-second-order logic. In Handbook of graph transformations, volume 1: Foundations, G.Rozenberg ed., 1997, in press.","DOI":"10.1142\/9789812384720_0005"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"B. Courcelle. On the expression of graph properties in some fragments of monadic-second-order logic. In Descriptive complexity and finite models, N. Immerman and Ph. Kolaitis eds., Contemporary Mathematics, AMS, 1997, in press.","DOI":"10.1090\/dimacs\/031\/02"},{"key":"6_CR9","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle, M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoret. Comput. Sci. 109:49\u201382, 1993","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR10","unstructured":"R. Fagin. Generalized first-order spectra and polynomial time recognizable sets. In Complexity of Computation R. Karp ed., SIAM-AMS proceedings 7:43\u201373, 1974"},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90218-I","volume":"116","author":"R. Fagin","year":"1993","unstructured":"R. Fagin. Finite model theory \u2014 a personal perspective. Theoret. Comput. Sci. 116:3\u201331, 1993","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and non local properties. Logic Colloquium'81, J. Stern ed., North-Holland, pp. 105\u2013135, 1982","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"6_CR13","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM J. Comput. 16:760\u2013778, 1987","journal-title":"SIAM J. Comput."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"D. Kaller. Definability equals recognizability of partial 3-trees. newblock Proceedings of WG'96, Como, Italy, Lecture Notes in Computer Science. 1997, to appear.","DOI":"10.1007\/3-540-62559-3_20"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"V. Kabanets. Recognizability equals definability for partial k-paths, 1996, Submitted","DOI":"10.1007\/3-540-63165-8_233"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"J. Makowsky Model theory and computer science: an appetizer. Chapter I.6 of Handbook of Logic in Computer Science, Vol. 1, S. Abramsky et al. eds., Oxford University Press, 1992.","DOI":"10.1093\/oso\/9780198537359.003.0006"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"J. Makowsky, Y. Pnueli, Arity vs. Alternation in second-order logic. Logical Foundations of Computer Science, A. Nerode, Y. Matiyasevich eds., Lecture Notes in Computer Science 813:240\u2013252, 1994","DOI":"10.1007\/3-540-58140-5_24"},{"key":"6_CR18","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0168-0072(91)90054-P","volume":"53","author":"D. Seese","year":"1991","unstructured":"D. Seese The structure of the models of decidable monadic theories of graphs. Ann. Pure Applied Logic 53:169\u2013195, 1991","journal-title":"Ann. Pure Applied Logic"},{"key":"6_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer The polynomial-time hierarchy. Theoret. Comput. Sci. 3:1\u201322, 1977","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63045-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T18:01:37Z","timestamp":1713636097000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63045-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540630456","9783540690658"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-63045-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"25 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}