{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T08:27:16Z","timestamp":1649147236029},"reference-count":8,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T00:00:00Z","timestamp":1211932800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,1]]},"DOI":"10.1007\/s00224-008-9120-3","type":"journal-article","created":{"date-parts":[[2008,5,27]],"date-time":"2008-05-27T15:32:50Z","timestamp":1211902370000},"page":"2-8","source":"Crossref","is-referenced-by-count":3,"title":["Generic Complexity of Presburger Arithmetic"],"prefix":"10.1007","volume":"46","author":[{"given":"Alexander N.","family":"Rybalov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,28]]},"reference":[{"key":"9120_CR1","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13, 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"9120_CR2","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. In: Proceedings of 44th FOCS, IEEE, pp. 308\u2013317 (2003)","DOI":"10.1109\/SFCS.2003.1238205"},{"key":"9120_CR3","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: Average-case complexity. Electronic Colloquium on Computational Complexity, Report No. 73 (2006)","DOI":"10.1561\/9781933019970"},{"key":"9120_CR4","unstructured":"Fischer, M.J., Rabin, M.O.: Super-exponential complexity of Presburger arithmetic. In: Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27\u201341 (1974)"},{"issue":"4","key":"9120_CR5","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1305\/ndjfl\/1168352664","volume":"47","author":"J.D. Hamkins","year":"2006","unstructured":"Hamkins, J.D., Miasnikov, A.: The halting problem is decidable on a set of asymptotic probability one. Notre Dame J. Form. Log. 47(4), 515\u2013524 (2006)","journal-title":"Notre Dame J. Form. Log."},{"issue":"2","key":"9120_CR6","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0021-8693(03)00167-4","volume":"264","author":"I. Kapovich","year":"2003","unstructured":"Kapovich, I., Myasnikov, A., Schupp, P., Shpilrain, V.: Generic-case complexity, decision problems in group theory and random walks. J. Algebra 264(2), 665\u2013694 (2003)","journal-title":"J. Algebra"},{"key":"9120_CR7","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/j.aim.2003.02.001","volume":"190","author":"I. Kapovich","year":"2005","unstructured":"Kapovich, I., Myasnikov, A., Schupp, P., Shpilrain, V.: Average-case complexity for the word and membership problems in group theory. Adv. Math. 190, 343\u2013359 (2005)","journal-title":"Adv. Math."},{"key":"9120_CR8","volume-title":"The Art of Computer Programming, vol. 3: Sorting and Searching","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 3: Sorting and Searching. Addison-Wesley, Reading (1998)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9120-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9120-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9120-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,5]],"date-time":"2020-05-05T23:48:57Z","timestamp":1588722537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9120-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,28]]},"references-count":8,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["9120"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9120-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5,28]]}}}