{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T12:49:44Z","timestamp":1649162984071},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1983,12,1]],"date-time":"1983-12-01T00:00:00Z","timestamp":439084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Arch math Logik"],"published-print":{"date-parts":[[1983,12]]},"DOI":"10.1007\/bf02023011","type":"journal-article","created":{"date-parts":[[2005,8,12]],"date-time":"2005-08-12T08:01:33Z","timestamp":1123833693000},"page":"37-54","source":"Crossref","is-referenced-by-count":1,"title":["Natural limitations of decision procedures for arithmetic with bounded quantifiers"],"prefix":"10.1007","volume":"23","author":[{"given":"Daniele","family":"Mundici","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02023011_CR1","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms, Reading, MA: Addison-Wesley 1974."},{"key":"BF02023011_CR2","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"C.H. Bennet","year":"1973","unstructured":"Bennet, C.H.: Logical reversibility of computation. IBM J. Res. Develop.17, 525\u2013534 (1973).","journal-title":"IBM J. Res. Develop."},{"key":"BF02023011_CR3","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/BF01011339","volume":"22.5","author":"P. Benioff","year":"1980","unstructured":"Benioff, P.: The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. J. Statistical Phys.22.5, 563\u2013591 (1980).","journal-title":"J. Statistical Phys."},{"key":"BF02023011_CR4","doi-asserted-by":"crossref","unstructured":"Benioff, P.: Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: application to Turing machines. In: Proceedings of MIT Conference on Physics of Computation, May 6\u20138, 1981. Cambridge, MA (to appear in the International Journal of Theoretical Physics).","DOI":"10.1007\/BF01857725"},{"key":"BF02023011_CR5","volume-title":"A course in mathematical logic","author":"J.L. Bell","year":"1977","unstructured":"Bell, J.L., Machover, M.: A course in mathematical logic. Amsterdam: North-Holland 1977."},{"key":"BF02023011_CR6","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/S0022-0000(75)80060-2","volume":"11","author":"A. Ehrenfeucht","year":"1975","unstructured":"Ehrenfeucht, A.: Practical decidability. J. Comp. Syst. Sci.11, 392\u2013396 (1975).","journal-title":"J. Comp. Syst. Sci."},{"key":"BF02023011_CR7","first-page":"27","volume":"7","author":"M.J. Fischer","year":"1974","unstructured":"Fischer, M.J., Rabin, M.O.: Super-exponential complexity of Presburger arithmetic. SIAM-AMS Proceedings7, 27\u201341 (1974).","journal-title":"SIAM-AMS Proceedings"},{"key":"BF02023011_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-46178-1","volume-title":"Enumerability, decidability, computability","author":"H. Hermes","year":"1969","unstructured":"Hermes, H.: Enumerability, decidability, computability, 2nd edit. Berlin, Heidelberg, New York: Springer 1969.","edition":"2nd edit."},{"key":"BF02023011_CR9","first-page":"477","volume":"2","author":"A.R. Meyer","year":"1974","unstructured":"Meyer, A.R.: The inherent complexity of theories of ordered sets. In: Proceedings of the Int. Cong. Math., Vancouver 1974, Vol. 2, Canadian Math. Congress 477\u2013482.","journal-title":"Proceedings of the Int. Cong. Math., Vancouver"},{"key":"BF02023011_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9452-5","volume-title":"Mathematical logic","author":"J.D. Monk","year":"1976","unstructured":"Monk, J.D.: Mathematical logic, Berlin, Heidelberg, New York: Springer 1976."},{"key":"BF02023011_CR11","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02721331","volume":"61 B","author":"D. Mundici","year":"1981","unstructured":"Mundici, D.: Irreversibility, uncertainty, relativity, and computer limitations. Il Nuovo Cimento, Europhysics Journal61 B, 297\u2013305 (1981).","journal-title":"Il Nuovo Cimento, Europhysics Journal"},{"issue":"4","key":"BF02023011_CR12","first-page":"261","volume":"3","author":"D. Mundici","year":"1982","unstructured":"Mundici, D.: Complexity of Craig's interpolation. Ann. Soc. Math. Pol. Series IV: Fundamenta Informaticae V.3\/4, 261\u2013278 (1982).","journal-title":"Ann. Soc. Math. Pol. Series IV: Fundamenta Informaticae"},{"key":"BF02023011_CR13","volume-title":"Perspectives in mathematical logic","author":"D. Mundici","year":"1983","unstructured":"Mundici, D.: Quantifiers: an overview. In: Abstract model theory and strong logics (Barwise, J. and Feferman, S., eds.). Perspectives in mathematical logic. Berlin, Heidelberg, New York: Springer (to appear) 1983."},{"key":"BF02023011_CR14","first-page":"231","volume":"263","author":"D. Mundici","year":"1981","unstructured":"Mundici, D.: Robinson's consistency theorem in soft model theory. Trans. Am. Math. Soc.263, 231\u2013241 (1981).","journal-title":"Trans. Am. Math. Soc."},{"key":"BF02023011_CR15","doi-asserted-by":"crossref","unstructured":"Mundici, D.: Compactness = JEP in any logic. Fund. Math.116 (to appear) (1983).","DOI":"10.4064\/fm-116-2-99-108"},{"key":"BF02023011_CR16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1090\/S0002-9947-1982-0642332-1","volume":"270","author":"D. Mundici","year":"1982","unstructured":"Mundici, D.: Duality between logics and equivalence relations. Trans. Am. Math. Soc.270, 111\u2013129 (1982).","journal-title":"Trans. Am. Math. Soc."},{"key":"BF02023011_CR17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF02023010","volume":"23","author":"D. Mundici","year":"1983","unstructured":"Mundici, D.: A lower bound for the complexity of Craig's interpolants in sentential logic. Arch. math. Logik23, 27\u201336 (1983).","journal-title":"Arch. math. Logik"},{"key":"BF02023011_CR18","volume-title":"An introduction to the general theory of algorithms","author":"M. Machtey","year":"1979","unstructured":"Machtey, M., Young, P.: An introduction to the general theory of algorithms, 3rd printing. Amsterdam: North-Holland 1979.","edition":"3rd printing"},{"key":"BF02023011_CR19","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/S0049-237X(08)71116-9","volume-title":"Handbook of mathematical logic","author":"M.O. Rabin","year":"1977","unstructured":"Rabin, M.O.: Decidable theories. In: Handbook of mathematical logic (Barwise, J., ed.), pp. 595\u2013630. Amsterdam: North-Holland 1977."},{"key":"BF02023011_CR20","unstructured":"Stockmeyer, L.J.: The complexity of decision problems in automata theory and logic. MIT Proj. MAC Technical Report 133 (1974)."}],"container-title":["Archiv f\u00fcr Mathematische Logik und Grundlagenforschung"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02023011.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02023011\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02023011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T18:39:56Z","timestamp":1557772796000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02023011"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["BF02023011"],"URL":"https:\/\/doi.org\/10.1007\/bf02023011","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,12]]}}}