{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:35:20Z","timestamp":1725489320259},"publisher-location":"Berlin, Heidelberg","reference-count":7,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540745099"},{"type":"electronic","value":"9783540745105"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74510-5_36","type":"book-chapter","created":{"date-parts":[[2007,8,21]],"date-time":"2007-08-21T15:11:35Z","timestamp":1187709095000},"page":"356-361","source":"Crossref","is-referenced-by-count":1,"title":["Generic Complexity of Presburger Arithmetic"],"prefix":"10.1007","author":[{"given":"Alexander N.","family":"Rybalov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"publisher","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 Journal on Computing\u00a013, 850\u2013864 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR2","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":"36_CR3","first-page":"308","volume-title":"Proceedings of 44th FOCS","author":"A. Bogdanov","year":"2003","unstructured":"Bogdanov, A., Trevisan, L.: On Worst-Case to Average-Case Reductions for NP Problems. In: Proceedings of 44th FOCS, pp. 308\u2013317. IEEE, Los Alamitos (2003)"},{"key":"36_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.\u00a07, pp. 27\u201341 (1974)"},{"issue":"4","key":"36_CR5","doi-asserted-by":"publisher","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 Journal of Formal Logic\u00a047(4), 515\u2013524 (2006)","journal-title":"Notre Dame Journal of Formal Logic"},{"issue":"2","key":"36_CR6","doi-asserted-by":"publisher","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\u00a0264(2), 665\u2013694 (2003)","journal-title":"J. Algebra"},{"key":"36_CR7","doi-asserted-by":"publisher","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. Advances in Mathematics\u00a0190, 343\u2013359 (2005)","journal-title":"Advances in Mathematics"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74510-5_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:22:50Z","timestamp":1605763370000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74510-5_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540745099","9783540745105"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74510-5_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}