{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:37:51Z","timestamp":1780382271149,"version":"3.54.1"},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":649,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the following problem: Given a proof of the Skolemization of a formula<jats:italic>F<\/jats:italic>, what is the length of the shortest proof of<jats:italic>F<\/jats:italic>? For the restriction of this question to cut-free proofs we prove corresponding exponential upper and lower bounds.<\/jats:p>","DOI":"10.2178\/jsl\/1333566645","type":"journal-article","created":{"date-parts":[[2012,4,4]],"date-time":"2012-04-04T19:26:53Z","timestamp":1333567613000},"page":"669-686","source":"Crossref","is-referenced-by-count":17,"title":["On the complexity of proof deskolemization"],"prefix":"10.1017","volume":"77","author":[{"given":"Matthias","family":"Baaz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Hetzl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Weller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200000815_ref010","first-page":"104","article-title":"Lower bounds on Herbrand's theorem","volume":"75","author":"Statman","year":"1979","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S0022481200000815_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF00370646"},{"key":"S0022481200000815_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/772062.772068"},{"key":"S0022481200000815_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00026-8"},{"key":"S0022481200000815_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF00881956"},{"key":"S0022481200000815_ref004","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1999.0359"},{"key":"S0022481200000815_ref005","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/oso\/9780198536901.001.0001","volume-title":"Arithmetic, proof theory and computational complexity","author":"Clote","year":"1993"},{"key":"S0022481200000815_ref011","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139168717"},{"key":"S0022481200000815_ref002","doi-asserted-by":"crossref","first-page":"353","DOI":"10.3233\/FI-1994-2044","article-title":"Skolemization and proof complexity","volume":"20","author":"Baaz","year":"1994","journal-title":"Fundamenta Informaticae"},{"key":"S0022481200000815_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-86896-2"},{"key":"S0022481200000815_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201363"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200000815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,22]],"date-time":"2024-04-22T20:13:12Z","timestamp":1713816792000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200000815\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["S0022481200000815"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1333566645","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}