{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:50Z","timestamp":1725663770057},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540544876"},{"type":"electronic","value":"9783540384014"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54487-9_60","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:53:28Z","timestamp":1330192408000},"page":"195-233","source":"Crossref","is-referenced-by-count":5,"title":["RAM with compact memory: a realistic and robust model of computation"],"prefix":"10.1007","author":[{"given":"Etienne","family":"Grandjean","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. M.","family":"Robson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"12_CR1","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1974","unstructured":"A.V. AHO, J.E. HOPCROFT and J.D. ULLMAN, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"D. ANGLUIN and L. VALIANT, Fast probabilistic algorithms for hamiltonian circuits and matchings, J. Comput. System Sci. 18 (1979), pp. 155\u2013193.","journal-title":"J. Comput. System Sci."},{"key":"12_CR3","unstructured":"R.G. ARCHIBALD, Introduction to the theory of numbers, Merrill, 1970."},{"key":"12_CR4","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"S.A. COOK and R.A. RECKHOW, Time bounded random access machines, J. Comput. System Sci. 7 (1973), pp. 354\u2013375.","journal-title":"J. Comput. System Sci."},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"3","author":"W.F. Dowling","year":"1984","unstructured":"W.F. DOWLING and J.H. GALLIER, Linear-time algorithms for testing the satisfiability of propositional Horn formulas, J. Logic Prog. 3 (1984), pp. 267\u2013284.","journal-title":"J. Logic Prog."},{"key":"12_CR6","first-page":"453","volume":"18","author":"E.W. Dijkstra","year":"1975","unstructured":"E.W. DIJKSTRA, Guarded commands, nondeterminacy and the formal derivation of programs, Comm. A.C.M. 18 (1975), pp. 453\u2013457.","journal-title":"Comm. A.C.M."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(89)90117-8","volume":"30","author":"P. Emde Boas Van","year":"1989","unstructured":"P. Van EMDE BOAS, Space measures for storage modification machines, Inf. Proc. Letters, 30 (1989), pp. 103\u2013110.","journal-title":"Inf. Proc. Letters"},{"key":"12_CR8","unstructured":"E. GRAEDEL, On the notion of linear time, Proc. 3rd Italian Conf. Theoret. Comput. Sci., Mantova 1989, World Scientific Publ. Co., 323\u2013334 (also to appear in a Special Issue of Internat. Journal of Foundations Comput. Sci.)."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01699468","volume":"18","author":"E. Grandjean","year":"1985","unstructured":"E. GRANDJEAN, Universal quantifiers and time complexity of random access machines, Math. Syst. Th. 18, (1985), pp. 171\u2013187.","journal-title":"Math. Syst. Th."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1137\/0219028","volume":"19","author":"E. Grandjean","year":"1990","unstructured":"E. GRANDJEAN, A nontrivial lower bound for an NP problem on automata, SIAM J. Comput. 19, (1990), pp. 438\u2013451.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"12_CR11","first-page":"238","volume":"11","author":"E. Grandjean","year":"1990","unstructured":"E. GRANDJEAN, RAMs with polynomially compact memory are efficiently simulated by RAMs with almost linearly compact memory, Abstracts of A.M.S. 90T-68-33 Issue 67 vol. 11 n. 2 (March 1990) p. 238.","journal-title":"Abstracts of A.M.S. 90T-68-33 Issue 67"},{"issue":"4","key":"12_CR12","first-page":"357","volume":"11","author":"E. Grandjean","year":"1990","unstructured":"E. GRANDJEAN, RAMs can be simulated in linear time by RAMs with compact memory, Abstracts of A.M.S. 90T-68-146 Issue 70 vol. 11 n. 4 (August 1990) p. 357.","journal-title":"Abstracts of A.M.S. 90T-68-146 Issue 70"},{"key":"12_CR13","unstructured":"E. GRANDJEAN, Invariance properties of RAMs and linear time, Technical Report L.I.U.C. Univ. Caen FRANCE 90-11 (december 1990)."},{"issue":"2","key":"12_CR14","first-page":"238","volume":"11","author":"E. Grandjean","year":"1990","unstructured":"E. GRANDJEAN and J.M. ROBSON, RAM with compact memory, Abstracts of A.M.S. 90T-68-34 Issue 67 vol. 11 n. 2 (March 1990) p. 238.","journal-title":"Abstracts of A.M.S. 90T-68-34 Issue 67"},{"key":"12_CR15","first-page":"71","volume":"35","author":"Y. Gurevich","year":"1988","unstructured":"Y. GUREVICH, Kolmogorov machines and related issues: The column on logic in computer science, Bull. EATCS 35 (1988), pp. 71\u201382.","journal-title":"Bull. EATCS"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Y. GUREVICH and S. SHELAH, Nearly linear time, in Meyer Taitslin (Eds.), Springer-Verlag Berlin, 1989, LNCS 363, pp. 108\u2013118","DOI":"10.1007\/3-540-51237-3_10"},{"key":"12_CR17","volume-title":"Introduction to automata theory, languages and computation","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. HOPCROFT and J. D. ULLMAN, Introduction to automata theory, languages and computation, Addison-Wesley, Reading, MA, 1979."},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0217005","volume":"17","author":"J. Katajainen","year":"1988","unstructured":"J. KATAJAINEN, J. van LEUWEN and M. PENTTONEN, Fast simulation of Turing machines by random access machines, SIAM J. Comput. 17 (1988), pp. 77\u201388.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"12_CR19","first-page":"3","volume":"13","author":"A.N. Kolmogorov","year":"1958","unstructured":"A.N. KOLMOGOROV and V.A. USPENSKY, On the definition of an algorithm, Uspekhi Mat. Nauk 13:4 (1958), pp. 3\u201328 (Russian) or AMS translation, ser. 2, vol 21 (1963), pp. 217\u2013245.","journal-title":"Uspekhi Mat. Nauk"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(88)90124-X","volume":"29","author":"M. Minoux","year":"1988","unstructured":"M. MINOUX, LTUR: a simplified linear-time resolution algorithm for Horn formulae and computer implementation, Inf. Proc. Letters 29 (1988) pp. 1\u201312.","journal-title":"Inf. Proc. Letters"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0020-0190(90)90133-I","volume":"34","author":"J.M. Robson","year":"1990","unstructured":"J.M. ROBSON, Random access machines with multi-dimensional memories, Inf. Proc. Letters 34 (1990) pp. 265\u2013266.","journal-title":"Inf. Proc. Letters"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(82)90129-6","volume":"14","author":"A. Schmitt","year":"1982","unstructured":"A. SCHMITT, On the computational power of the floor function, Inf. Proc. Letters 14 (1982), pp 1\u20133.","journal-title":"Inf. Proc. Letters"},{"key":"12_CR23","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1145\/322047.322060","volume":"25","author":"C.P. Schnorr","year":"1978","unstructured":"C.P. SCHNORR, Satisfiability is quasilinear complete in NQL, J. Assoc. Comput. Mach., 25 (1978), pp. 136\u2013145.","journal-title":"J. Assoc. Comput. Mach."},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A. Sch\u00f6nhage","year":"1980","unstructured":"A. SCH\u00d6NHAGE, Storage modification machines, SIAM J. Comput. 9 (1980), pp. 490\u2013508.","journal-title":"SIAM J. Comput."},{"key":"12_CR25","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1145\/44483.44492","volume":"35","author":"A. Sch\u00f6nhage","year":"1988","unstructured":"A. SCH\u00d6NHAGE, A nonlinear lower bound for random access machines under logarithmic cost, J. Assoc. Comput. Mach. 35 (1988), pp. 748\u2013754.","journal-title":"J. Assoc. Comput. Mach."},{"key":"12_CR26","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(88)90052-1","volume":"77","author":"C. Slot","year":"1988","unstructured":"C. SLOT and P. van EMDE BOAS, The problem of space invariance for sequential machines, Inform. and Comput. 77 (1988), pp.93\u2013122.","journal-title":"Inform. and Comput."},{"key":"12_CR27","first-page":"163","volume-title":"Proc. IFIP Congress 83","author":"J. WIEDERMANN","year":"1983","unstructured":"J. WIEDERMANN, Deterministic and nondeterministic simulation of the RAM by the Turing machine, in Proc. IFIP Congress 83, R.E.A. Mason ed., North Holland, Amsterdam 1983, pp. 163\u2013168."},{"key":"12_CR28","unstructured":"J. WIEDERMANN, Normalizing and accelerating RAM computations and the problem of reasonable space measures, TR OPS-3 \/ 1990 (June 1990), Dpt of Programming Systems, Bratislava, Czechoslovakia."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54487-9_60.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:55:05Z","timestamp":1605628505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54487-9_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544876","9783540384014"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-54487-9_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}