{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:18:56Z","timestamp":1672291136891},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            We show how to reduce the time overhead for implementing two-way movement on a singly linked list to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03f5<\/jats:sup>\n            ) per operation without modifying the list and without making use of storage other than a finite number of pointers into the list. We also prove a matching lower bound.These results add precision to the intuitive feeling that doubly linked lists are more efficient than singly linked lists, and quantify the efficiency gap in a read-only situation. We further analyze the number of points of access into the list (pointers) necessary for obtaining a desired value of \u03f5. We obtain tight tradeoffs which also separate the amortized and worst-case settings.Our upper bound implies that read-only programs with singly-linked input can do string matching much faster than previously expected.\n          <\/jats:p>","DOI":"10.1145\/1162349.1162353","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"681-705","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Backing up in singly linked lists"],"prefix":"10.1145","volume":"53","author":[{"given":"Amir M.","family":"Ben-Amram","sequence":"first","affiliation":[{"name":"The Academic College of Tel-Aviv Yaffo, Tel-Aviv, Israel"}]},{"given":"Holger","family":"Petersen","sequence":"additional","affiliation":[{"name":"University of Stuttgart, Stuttgart"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146666"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 14th Annual Symposium on Switching and Automata Theory, R. V. Book, Ed. IEEE Computer Society Press","author":"Chandra A. K.","year":"1973"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0020-0190(76)90050-8","article-title":"Two fast simulations which imply some fast string matching and palindrome-recognition algorithms","volume":"4","author":"Galil Z.","year":"1976","journal-title":"Inf. Process. Lett."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/0022-0000(83)90002-8","article-title":"Time-space-optimal string matching","volume":"26","author":"Galil Z.","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_5_1","unstructured":"Horowitz E. and Sahni S. 1983. Fundamentals of Data Structures. Computer Science Press Rockville MA.  Horowitz E. and Sahni S. 1983. Fundamentals of Data Structures. Computer Science Press Rockville MA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Jones N. D. 1997. Computability and Complexity---From a Programming Perspective. MIT Press Cambridge MA.   Jones N. D. 1997. Computability and Complexity---From a Programming Perspective. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/2003.001.0001"},{"key":"e_1_2_1_7_1","unstructured":"Jones N. D. 1998. Must fast pattern matchers be impure&quest; Note distributed during Dagstuhl Seminar 9823 \u201cPrograms: Improvements Complexity and Meanings\u201d June 8--12.  Jones N. D. 1998. Must fast pattern matchers be impure&quest; Note distributed during Dagstuhl Seminar 9823 \u201cPrograms: Improvements Complexity and Meanings\u201d June 8--12."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth D. E.","year":"1977","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Li M. and Vit\u00e1nyi P. 1997. An Introduction to Kolmogorov Complexity and its Applications 2nd ed. Springer-Verlag Berlin-Heidelberg-New York.   Li M. and Vit\u00e1nyi P. 1997. An Introduction to Kolmogorov Complexity and its Applications 2nd ed. Springer-Verlag Berlin-Heidelberg-New York.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"2719","author":"Matias Y."},{"key":"e_1_2_1_11_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 6th Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Meyer Auf Der Heide F."},{"key":"e_1_2_1_12_1","volume-title":"Record of Project MAC Conference on Concurrent Systems and Parallel Computation (Woods Hole). 119--128","author":"Paterson M. S."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0022-0000(81)90009-X","article-title":"An information-theoretic approach to time bounds for on-line computation","volume":"23","author":"Paul W. J.","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/244795.244798"},{"key":"e_1_2_1_15_1","volume-title":"Conference Record of the 6th Annual ACM Symposium on Principles of Programming Languages (POPL'79)","author":"Swamy S."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1162349.1162353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:56:31Z","timestamp":1672257391000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1162349.1162353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1162349.1162353"],"URL":"https:\/\/doi.org\/10.1145\/1162349.1162353","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}