{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:14:09Z","timestamp":1725455649296},"publisher-location":"Berlin\/Heidelberg","reference-count":9,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540571841"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0022566","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:14:45Z","timestamp":1131862485000},"page":"184-186","source":"Crossref","is-referenced-by-count":1,"title":["Double exponential inseparability of Robinson subsystem Q+ from the unsatisfiable sentences in the language of addition"],"prefix":"10.1007","author":[{"given":"Giovanni","family":"Faglia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0304-3975(80)90037-7","volume":"11","author":"L. Berman","year":"1980","unstructured":"Berman L.: The Complexity of Logical Theories. Theoretical Computer Science, (1980) 11:71\u201377.","journal-title":"Theoretical Computer Science"},{"key":"20_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","volume":"48","author":"K.J. Compton","year":"1990","unstructured":"Compton, K.J., Henson, C.W.: A uniform method for proving lower bounds on the computational complexity of logical theories. Annals of Pure and Applied Logic, 48 (1990) 1\u201379.","journal-title":"Annals of Pure and Applied Logic"},{"key":"20_CR3","volume-title":"PhD thesis","author":"G. Faglia","year":"1993","unstructured":"Faglia, G.: Double exponential inseparability of theories of addition. PhD thesis, Dottorato di Ricerca in Informatica, Universit\u00e0 di Torino e Milano, Via Comelico 39, I-20135 Milano MI, Italy, February 1993. In Italian."},{"key":"20_CR4","unstructured":"Fischer, M.J., Rabin, M.: Super-Exponential Complexity of Presburger Arithmetic. In Complexity of Computation, SIAM-AMS, (1974) 27\u201348."},{"key":"20_CR5","unstructured":"Hilbert, D., Bernays, P.: Grundlagen der Mathematik, volume 1. Springer, (1934)."},{"key":"20_CR6","unstructured":"Presburger M.: \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die Addition als einzige Operation hervortritt. In Comptes-Rendus du 1er Congr\u00e8s des Math\u00e9maticiens des Pays Slavs, (1929)."},{"key":"20_CR7","first-page":"729","volume":"1","author":"R.M. Robinson","year":"1950","unstructured":"Robinson, R.M.: An Essentially Undecidable Axiom System. In Proceedings of the International Congress of Mathematicians. Cambridge, 1, (1950) 729\u201330.","journal-title":"Proceedings of the International Congress of Mathematicians. Cambridge"},{"key":"20_CR8","unstructured":"Tarski, A., Mostowsky, A., Robinson, R.: Undecidable Theories. North-Holland, (1953)."},{"key":"20_CR9","unstructured":"Young, P.: G\u00f6del Theorems, Exponential Difficulty and Undecidability of Arithmetic Theories: An Exposition. In Proceedings of Symposia in Pure Mathematics, American Mathematical Society, (1985) 503\u2013522."}],"container-title":["Lecture Notes in Computer Science","Computational Logic and Proof Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022566.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:49:03Z","timestamp":1607550543000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022566"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540571841"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/bfb0022566","relation":{},"subject":[]}}