{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:17:25Z","timestamp":1725466645521},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642316524"},{"type":"electronic","value":"9783642316531"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31653-1_16","type":"book-chapter","created":{"date-parts":[[2012,7,14]],"date-time":"2012-07-14T09:51:39Z","timestamp":1342259499000},"page":"166-177","source":"Crossref","is-referenced-by-count":1,"title":["Unary Coded NP-Complete Languages in ASPACE (log log n)"],"prefix":"10.1007","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Pardubsk\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-540-95891-8_28","volume-title":"SOFSEM 2009: Theory and Practice of Computer Science","author":"V. Geffert","year":"2009","unstructured":"Geffert, V., Pardubsk\u00e1, D.: Factoring and Testing Primes in Small Space. In: Nielsen, M., Ku\u010dera, A., Miltersen, P.B., Palamidessi, C., T\u016fma, P., Valencia, F. (eds.) SOFSEM 2009. LNCS, vol.\u00a05404, pp. 291\u2013302. Springer, Heidelberg (2009)"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: Primes is in\u00a0P. Ann. of Math.\u00a0160, 781\u2013793 (2004)","journal-title":"Ann. of Math."},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., Kozen, D., Stockmeyer, L.: Alternation. J.\u00a0Assoc. Comput. Mach.\u00a028, 114\u2013133 (1981)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"Savitch, W.: Relationships between nondeterministic and deterministic tape complexities. J.\u00a0Comput. System Sci.\u00a04, 177\u2013192 (1970)","journal-title":"J.\u00a0Comput. System Sci."},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/inco.1997.2682","volume":"142","author":"V. Geffert","year":"1998","unstructured":"Geffert, V.: Bridging across the log(n) space frontier. Inform. & Comput.\u00a0142, 127\u2013158 (1998)","journal-title":"Inform. & Comput."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1137\/0222011","volume":"22","author":"K. Iwama","year":"1993","unstructured":"Iwama, K.: ASPACE(o(loglogn)) is regular. SIAM J. Comput.\u00a022, 136\u2013146 (1993)","journal-title":"SIAM J. Comput."},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1137\/S0097539793252444","volume":"25","author":"M. Li\u015bkiewicz","year":"1996","unstructured":"Li\u015bkiewicz, M., Reischuk, R.: The sublogarithmic alternating space world. SIAM J. Comput.\u00a025, 828\u2013861 (1996)","journal-title":"SIAM J. Comput."},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58355-6","volume-title":"Turing Machines with Sublogarithmic Space","author":"A. Szepietowski","year":"1994","unstructured":"Szepietowski, A.: Turing Machines with Sublogarithmic Space. LNCS, vol.\u00a0843. Springer, Heidelberg (1994)"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/3-540-51486-4_56","volume-title":"Mathematical Foundations of Computer Science 1989","author":"J. Hartmanis","year":"1989","unstructured":"Hartmanis, J., Ranjan, D.: Space Bounded Computations: Review and New Separation Results. In: Kreczmar, A., Mirkowska, G. (eds.) MFCS 1989. LNCS, vol.\u00a0379, pp. 49\u201366. Springer, Heidelberg (1989)"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0304-3975(91)90391-E","volume":"80","author":"R. Chang","year":"1991","unstructured":"Chang, R., Hartmanis, J., Ranjan, D.: Space bounded computations: Review and new separation results. Theoret. Comput. Sci.\u00a080, 289\u2013302 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1051\/ita:2001119","volume":"35","author":"A. Chiu","year":"2001","unstructured":"Chiu, A., Davida, G., Litow, B.: Division in logspace-uniform\u00a0NC\n                  1. RAIRO Inform. Th\u00e9or. Appl.\u00a035, 259\u2013275 (2001)","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(94)00021-2","volume":"50","author":"P. Dietz","year":"1994","unstructured":"Dietz, P., Macarie, I., Seiferas, J.: Bits and relative order from residues, space efficiently. Inform. Process. Lett.\u00a050, 123\u2013127 (1994)","journal-title":"Inform. Process. Lett."},{"key":"16_CR13","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1976)"},{"key":"16_CR14","unstructured":"Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Prentice Hall (2007)"},{"key":"16_CR15","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 2nd edn. Thomson Course Technology (2006)"},{"key":"16_CR16","unstructured":"Hardy, G., Wright, E.: An Introduction to the Theory of Numbers. Clarendon Press, Oxford (1995); (Reprint of 5th edn. 1979)"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Yan, S.: Number Theory for Computing. Springer (2002)","DOI":"10.1007\/978-3-662-04773-6"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31653-1_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:41:27Z","timestamp":1620128487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31653-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316524","9783642316531"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31653-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}