{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T04:40:01Z","timestamp":1737607201479,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540665366"},{"type":"electronic","value":"9783540481683"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"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":[[1999]]},"DOI":"10.1007\/3-540-48168-0_23","type":"book-chapter","created":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T11:30:26Z","timestamp":1196508626000},"page":"322-337","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["MonadicNLIN and Quantifier-Free Reductions"],"prefix":"10.1007","author":[{"given":"Clemens","family":"Lautemann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Weinzinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"S. Cosmadakis. Logical reducibility and monadic NP. In Proc. 34th IEEE Symp. on Foundations of Computer Science,pages 52\u201361,1993.","DOI":"10.1109\/SFCS.1993.366882"},{"key":"23_CR2","doi-asserted-by":"publisher","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 as relational structures. Discrete Applied Mathematics, 54:117\u2013149,1994.","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"B. Courcelle. On the expression of graph properties in some fragments of monadic second-order logic. In N. Immerman and P. Kolaitis,editors, Descriptive Complexity and Finite Models,pages 33\u201362. American Mathematical Society,1997.","DOI":"10.1090\/dimacs\/031\/02"},{"issue":"1-2","key":"23_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(94)00182-I","volume":"145","author":"N. Creignou","year":"1995","unstructured":"Nadia Creignou. The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness. Theoretical Computer Science,145(1-2):111\u2013145,10 July 1995.","journal-title":"Theoretical Computer Science"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1002\/malq.19870330107","volume":"33","author":"M. Rougemont de","year":"1987","unstructured":"M. de Rougemont. Second-order and inductive definability on finite structures. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 33:47\u201363,1987.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"23_CR6","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp,editor, Complexity of Computation, SIAM-AMS Proceedings, Vol. 7,pages 43\u201373,1974."},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. Monadic generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik,21:89\u201396,1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"E. Grandjean and F. Olive. Monadic logical definability of NP-complete problems. In Proc. 1994 of the Annual Conference of the EACSL,pages 190\u2013204,1994. Extended version submitted.","DOI":"10.1007\/BFb0022256"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"E. Grandjean and F. Olive. Monadic logical definability of NP-complete problems. submitted,1996.","DOI":"10.1007\/BFb0022256"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF01205055","volume":"4","author":"E. Grandjean","year":"1994","unstructured":"E. Grandjean. Invariance properties of RAMs and linear time. Computational Complexity,4:62\u2013106,1994.","journal-title":"Computational Complexity"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/S0097539791223206","volume":"23","author":"E. Grandjean","year":"1994","unstructured":"E. Grandjean. Linear time algorithms and NP-complete problems. SIAM Journal of Computing,23:573\u2013597,1994.","journal-title":"SIAM Journal of Computing"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02127798","volume":"16","author":"E. Grandjean","year":"1996","unstructured":"E. Grandjean. Sorting,linear time and the satisfiability problem. Annals of Mathematics and Artificial Intelligence,16:183\u2013236,1996.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"23_CR13","unstructured":"E. Grandjean and T. Schwentick. Machine-independent characterizations and complete problems for deterministic linear time. In preparation,1999."},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive and Computational Complexity. Springer,1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0168-0072(95)00030-5","volume":"79","author":"T. Schwentick","year":"1996","unstructured":"T. Schwentick. On winning Ehrenfeucht games and monadic NP. Annals of Pure and Applied Logic,79:61\u201392,1996.","journal-title":"Annals of Pure and Applied Logic"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48168-0_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T03:45:54Z","timestamp":1737603954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48168-0_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540665366","9783540481683"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-48168-0_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"13 May 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}