{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:58:44Z","timestamp":1725562724797},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642152047"},{"type":"electronic","value":"9783642152054"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15205-4_18","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T10:48:24Z","timestamp":1281696504000},"page":"200-214","source":"Crossref","is-referenced-by-count":3,"title":["On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT"],"prefix":"10.1007","author":[{"given":"Yijia","family":"Chen","sequence":"first","affiliation":[]},{"given":"J\u00f6rg","family":"Flum","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J.: A logic for PTIME and a parameterized halting problem. In: Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS 2009), pp. 397\u2013406 (2009)","DOI":"10.1109\/LICS.2009.11"},{"issue":"1","key":"18_CR2","doi-asserted-by":"publisher","first-page":"239","DOI":"10.2178\/jsl\/1264433918","volume":"75","author":"Y. Chen","year":"2010","unstructured":"Chen, Y., Flum, J.: On the complexity of G\u00f6del\u2019s proof predicate. The Journal of Symbolic Logic\u00a075(1), 239\u2013254 (2010)","journal-title":"The Journal of Symbolic Logic"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J.: On p-optimal proof systems and logics for PTIME. In: Gavoille, C. (ed.) ICALP 2010, Part II. LNCS, vol.\u00a06199, pp. 321\u2013332. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14162-1_27"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S. Cook","year":"1979","unstructured":"Cook, S., Reckhow, R.: The relative efficiency of propositional proof systems. The Journal of Symbolic Logic\u00a044, 36\u201350 (1979)","journal-title":"The Journal of Symbolic Logic"},{"key":"18_CR5","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"18_CR6","first-page":"372","volume-title":"Collected Works","author":"K. G\u00f6del","year":"2003","unstructured":"G\u00f6del, K.: Collected Works, vol.\u00a0VI, pp. 372\u2013376. Clarendon Press, Oxford (2003)"},{"key":"18_CR7","first-page":"1","volume-title":"Current Trends in Theoretical Computer Science","author":"Y. Gurevich","year":"1988","unstructured":"Gurevich, Y.: Logic and the challenge of computer science. In: Current Trends in Theoretical Computer Science, pp. 1\u201357. Computer Science Press, Rockville (1988)"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Messner, J.: Complete problems for promise classes by optimal proof systems for test sets. In: Proceedings of the 13th IEEE Conference on Computational Complexity (CCC 1998), pp. 132\u2013140 (1998)","DOI":"10.1109\/CCC.1998.694599"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations. The Journal of Symbolic Logic\u00a054, 1063\u20131088 (1989)","journal-title":"The Journal of Symbolic Logic"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/3-540-49116-3_51","volume-title":"STACS 99","author":"J. Messner","year":"1999","unstructured":"Messner, J.: On optimal algorithms and optimal proof systems. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 361\u2013372. Springer, Heidelberg (1999)"},{"key":"18_CR11","unstructured":"Monroe, H.: Speedup for natural problems. Electronic Colloquium on Computational Complexity, Report TR09-056 (2009)"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-540-30570-5_19","volume-title":"Database Theory - ICDT 2005","author":"A. Nash","year":"2004","unstructured":"Nash, A., Remmel, J., Vianu, V.: PTIME queries revisited. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, pp. 274\u2013288. Springer, Heidelberg (2004)"},{"issue":"1","key":"18_CR13","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0304-3975(01)00155-4","volume":"288","author":"Z. Sadowski","year":"2002","unstructured":"Sadowski, Z.: On an optimal propositional proof system and the structure of easy subsets. Theoretical Computer Science\u00a0288(1), 181\u2013193 (2002)","journal-title":"Theoretical Computer Science"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: On the complexity of bounded-variable queries. In: Proceedings of the 14th ACM Symposium on Principles of Database Systems (PODS 1995), pp. 266\u2013276 (1995)","DOI":"10.1145\/212433.212474"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15205-4_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:02:27Z","timestamp":1606168947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15205-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642152047","9783642152054"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15205-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}