{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:22:27Z","timestamp":1725456147617},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600176"},{"type":"electronic","value":"9783540494041"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0022256","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T01:12:29Z","timestamp":1132621949000},"page":"190-204","source":"Crossref","is-referenced-by-count":7,"title":["Monadic logical definability of NP-complete problems"],"prefix":"10.1007","author":[{"given":"Etienne","family":"Grandjean","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Olive","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"J.R. B\u00dcCHI, Weak second order arithmetic and finite automata, Z.Math. Logik Grundlagen Math. 6 (1960), pp.66\u201392.","journal-title":"Z.Math. Logik Grundlagen Math."},{"key":"14_CR2","unstructured":"R.FAGIN, Generalised first-order spectra and polynomial-time recognizable sets, in Complexity of Computations, R.Karp, ed., SIAM-AMS Proc. 7, 1974, pp.43\u201373."},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1142\/S0129054190000217","volume":"No 1","author":"E. Gr\u00e4del","year":"1990","unstructured":"E.GR\u00c4DEL, On the notion of linear time computability, International J. of Foundations of Computer Science, No 1 (1990), pp.295\u2013307.","journal-title":"International J. of Foundations of Computer Science"},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1137\/0217050","volume":"17","author":"E. Grandjean","year":"1988","unstructured":"E.GRANDJEAN, A natural NP-complete problem with a nontrivial lower bound, SIAM J.Comput., 17 (1988), pp.786\u2013809.","journal-title":"SIAM J.Comput."},{"key":"14_CR5","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1137\/0219028","volume":"19","author":"E. Grandjean","year":"1990","unstructured":"E.GRANDJEAN, A nontrivial lower bound for an NP problem on automata, SIAM J. Comput., 19 (1990), pp.438\u2013451.","journal-title":"SIAM J. Comput."},{"key":"14_CR6","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-56992-8_16","volume":"702","author":"E. Grandjean","year":"1993","unstructured":"E.GRANDJEAN, Linear time algorithms and NP-complete problems, Proc. CSL'92, Lect. Notes Comput. Sci. 702 (1993), pp. 248\u2013273, also to appear in SIAM J. on Computing.","journal-title":"Proc. CSL'92, Lect. Notes Comput. Sci."},{"key":"14_CR7","unstructured":"E.GRANDJEAN, Sorting, linear time and the satisfiability problem, to appear in special issue of Annals of Math. and Artificial Intelligence, 1995."},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Y.GUREVICH and S.SHELAH, Nearly linear time, Lect.notes Comput.Sci. 363 (1989), Springer-Verlag, pp.108\u2013118.","DOI":"10.1007\/3-540-51237-3_10"},{"key":"14_CR9","series-title":"Springer-Verlag Lecture Notes in Math. Vol.1104","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BFb0099486","volume-title":"Computation and Proof Theory","author":"Y. Gurevich","year":"1984","unstructured":"Y.GUREVICH, Toward Logic Tailored for Computational Complexity, Computation and Proof Theory, (M.M.Richter et. al., eds.). Springer-Verlag Lecture Notes in Math. Vol.1104, pp.175\u2013216, Springer-Verlag, New York\/Berlin, 1984."},{"key":"14_CR10","first-page":"1","volume-title":"Current Trends in Theorical Computer Science","author":"Y. Gurevich","year":"1986","unstructured":"Y.GUREVICH, Logic and the challenge of computer science, Current Trends in Theorical Computer Science, (E.Boerger Ed.), pp.1\u201355, Computer science, Rockville, MD, 1986."},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"N.IMMERMAN, Languages which capture complexity classes, 15th ACM Symp. on Theory of Computing, 1983, pp.347\u2013354; SIAM J. Comput., 16, No.4 (1987), 760\u2013778.","DOI":"10.1137\/0216051"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"N.IMMERMAN, Relational Queries Computable in Polynomial Time, 14th ACM STOC Symp., 1982, pp.147\u2013152. Also appeared in revised form in Information and Control, 68 (1986), pp.86\u2013104.","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"14_CR13","unstructured":"N.IMMERMAN, Descriptive and Computational Complexity, in J. Hartmanis ed., Computational Complexity Theory, Proc. of AMS Symposia in Appl. Math. 38 (1989), pp. 75\u201391."},{"key":"14_CR14","series-title":"Complexity of Computers Computations","volume-title":"IBM Symp.1972","author":"R.M. Karp","year":"1972","unstructured":"R.M.KARP, Reducibility among combinatorial problems, IBM Symp.1972, Complexity of Computers Computations, Plenum Press, New York, 1972."},{"key":"14_CR15","series-title":"Computer and Information Sciences","volume-title":"Technical report UCSC-CRL-90-48","author":"P.G. Kolaitis","year":"1990","unstructured":"P.G.KOLAITIS, M.N.THAKUR, Logical definability of NP-optimization problems, Technical report UCSC-CRL-90-48, Computer and Information Sciences, University of California, Santa-Cruz, 1990."},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J.F. Lynch","year":"1982","unstructured":"J.F.LYNCH, Complexity classes and theories of finite models, Math. Systems Theory, 15 (1982), pp.127\u2013144.","journal-title":"Math. Systems Theory"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/BF01276438","volume":"2","author":"J.F. Lynch","year":"1992","unstructured":"J.F.LYNCH, The quantifier structure of sentences that characterize nondeterministic time complexity, in Comput. Complexity, 2 (1992), pp.40\u201366.","journal-title":"Comput. Complexity"},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1145\/322047.322060","volume":"25","author":"C.P. Schnorr","year":"1978","unstructured":"Springer-VerlagC.P.SCHNORR, Satisfiability is quasilinear complete in NQL, J. ACM, 25 (1978), pp.136\u2013145.","journal-title":"J. ACM"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"M.VARDI, Complexity of Relational Query Languages, 14th ACM Symp. on Theory of Computation, 1982, pp.137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022256","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T22:42:56Z","timestamp":1586558576000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600176","9783540494041"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0022256","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}