{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T02:39:55Z","timestamp":1697942395476},"reference-count":9,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":24299,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1947,9]]},"abstract":"<jats:p>In the first paper of the above main title, one of us has proved that any formula of the first order predicate calculus is equivalent (as to being satisfiable or not) to some binary first order formula having a prefix of the form <jats:italic>(Ex<jats:sub>1<\/jats:sub>)(x<jats:sub>2<\/jats:sub>)(Ex<jats:sub>3<\/jats:sub>) \u2026 (x<jats:sub>n<\/jats:sub>)<\/jats:italic> and containing a single predicate variable. This result is an improvement of a theorem of Ackermann stating that any first order formula is equivalent to another with a prefix of the above form but saying nothing about the number of predicate variables appearing therein. Hence the question arises if other theorems reducing the decision problem to the satisfiability question of the first order formulas with a prefix of a special form can be improved in like manner. In the present paper we shall answer this question concerning G\u00f6del's reduction theorem stating that any first order formula is equivalent to another the prefix of which has the form<\/jats:p>","DOI":"10.2307\/2267211","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:58:08Z","timestamp":1146941888000},"page":"65-73","source":"Crossref","is-referenced-by-count":8,"title":["On the reduction of the decision problem"],"prefix":"10.1017","volume":"12","author":[{"given":"L\u00e1szl\u00f3","family":"Kalm\u00e1r","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e1nos","family":"Sur\u00e1nyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200075629_ref008","first-page":"51","article-title":"A logikai f\u00fcggv\u00e9nykalkulus eld\u00f6nt\u00e9s-probl\u00e9m\u00e1j\u00e1nak redukci\u00f3j\u00e1r\u00f3l (in Hungarian with German abstract: Zur Reduktion des Entschcidungsproblems des logischen Funktionenkalk\u00fcls)","volume":"50","author":"Sur\u00e1nyi","year":"1943","journal-title":"Matematikai \u00e9s fizikai lapok"},{"key":"S0022481200075629_ref004","first-page":"12","article-title":"Sur le probl\u00e8me fondamental de la logique math\u00e9matique","volume":"24","author":"Herbrand","year":"1931","journal-title":"Sprawozdania z posiedze\u0144 Towarzystwa Naukowego Warszawskiego"},{"key":"S0022481200075629_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BF01708881"},{"key":"S0022481200075629_ref001","first-page":"1","volume":"4","author":"Kalm\u00e1r","year":"1939","journal-title":"On the reduction of the decision problem, first paper, Ackermann prefix, a single binary predicate"},{"key":"S0022481200075629_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/BF01565424"},{"key":"S0022481200075629_ref005","first-page":"137","article-title":"Zw\u00fcckf\u00fchrung des Entscheidungsproblems auf den Fall von Formeln mit einer einzigen, bin\u00e4ren, Funktionsvariablen","volume":"4","author":"Kalm\u00e1r","year":"1936","journal-title":"Compositie mathematica"},{"key":"S0022481200075629_ref006","first-page":"1","article-title":"Einige Reduktionen des Entscheidungsproblems","author":"Skolem","year":"1936","journal-title":"Avhandlinger utgitt av det Norske Videnskaps-Akademi i Oslo"},{"key":"S0022481200075629_ref007","first-page":"121","article-title":"Zur Reduktion des Entscheidungsproblems","volume":"19","author":"Kalm\u00e1r","year":"1937","journal-title":"Norsk matematisk tidsskrift"},{"key":"S0022481200075629_ref009","first-page":"193","article-title":"Ein Satz \u00fcber Z\u00e4hlausdr\u016bcke","volume":"7","author":"Skolem","year":"1934","journal-title":"Acta scientiarum mathematicarum"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200075629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T10:56:50Z","timestamp":1559991410000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200075629\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1947,9]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1947,9]]}},"alternative-id":["S0022481200075629"],"URL":"https:\/\/doi.org\/10.2307\/2267211","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1947,9]]}}}