{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:14Z","timestamp":1742596814225,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569923"},{"type":"electronic","value":"9783540478904"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56992-8_19","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:59:47Z","timestamp":1330257587000},"page":"327-339","source":"Crossref","is-referenced-by-count":5,"title":["Logical definability of NP-optimisation problems with monadic auxiliary predicates"],"prefix":"10.1007","author":[{"given":"Clemens","family":"Lautemann","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Miklos Ajtai, Ronald Fagin, Reachability is harder for directed than for undirected finite graphs. JSL 55, pp. 113\u2013150.","DOI":"10.2307\/2274958"},{"key":"19_CR2","volume-title":"Proof verification and intractability of approximation problems (preliminary version)","author":"S. Arora","year":"1992","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy, Proof verification and intractability of approximation problems (preliminary version). Preprint, Computer Science Division, University of California, Berkeley, April 1992."},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Stefan Arnborg, Jens Lagergren, Detlev Seese, Easy problems for tree decomposable graphs. J. of Algorithms, 12, pp.308\u2013340.","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"19_CR4","unstructured":"Danilo Bruschi, Deborah Joseph, Paul Young, A structural overview of NP optimization problems. Rapporto Interno 75\/90, Dipartimento di Scienze dell'Informazione, Universit\u00e9 degli Studi di Milano."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Bruno Courcelle, On the expression of monadic second-order graph properties without quantifications over sets of edges. Proc. 5th Ann. IEEE Symposium on Logic in Computer Science, pp. 190\u2013196.","DOI":"10.1109\/LICS.1990.113745"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Michel de Rougemont, Second-order and inductive definability on finite structures. Zeitschrift f. math. Logik und Grundlagen d. Math. 33, pp. 47\u201363.","DOI":"10.1002\/malq.19870330107"},{"key":"19_CR7","unstructured":"Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. In Richard Karp, (Ed.):\u201dComplexity of Computation\u201d, SIAM-AMS Proc. 7, pp. 43\u201373."},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Ronald Fagin, Monadic generalized spectra. Zeitschr. f. math. Logik und Grundlagen d. Math. 21, pp. 89\u201396.","DOI":"10.1002\/malq.19750210112"},{"key":"19_CR9","unstructured":"Michael R. Garey, David S. Johnson, Computers and Intractability. Freeman, N.Y."},{"key":"19_CR10","unstructured":"Edmund Ihler, Approximation and existential second-order logic. Bericht 26, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg."},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Neil Immerman, Descriptive and computational complexity. In: Juris Hartmanis (Ed.):\u201dComputational Complexity Theory\u201d, Proc. AMS Symp. Appl. Math. 38, pp. 75\u201391.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"19_CR12","unstructured":"Dieter Knobloch, Zur Komplexit\u00e4t kombinatorischer Optimierungsprobleme. Diplomarbeit, FB Mathematik, Johannes Gutenberg-Universit\u00e4t Mainz."},{"key":"19_CR13","unstructured":"Phokion G. Kolaitis, Madhukar N. Thakur, Logical definability of NP optimization problems. Technical Report UCSC-CRL-90-48, Computer Research Laboratory, University of California, Santa Cruz."},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Phokion G. Kolaitis, Madhukar N. Thakur, Approximation properties of NP minimization classes. Proc. 7th Structure in Complexity Theory Conference, pp. 353\u2013366.","DOI":"10.1109\/SCT.1991.160280"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"James F. Lynch, Complexity Classes and Theories of Finite Models. Math. Syst. Theory 15, pp. 127\u2013144.","DOI":"10.1007\/BF01786976"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Alessandro Panconesi, Desh Ranjan, Quantifiers and approximation (extended abstract). Proc. 22nd ACM STOC, pp. 446\u2013456.","DOI":"10.1145\/100216.100275"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Christos H. Papadimitriou, Mihalis Yannakakis, Optimization, approximation, and complexity classes. JCSS 43, pp. 425\u2013440.","DOI":"10.1016\/0022-0000(91)90023-X"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56992-8_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:59:10Z","timestamp":1742594350000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56992-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569923","9783540478904"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-56992-8_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}