Article

Free access

Backing up in singly linked lists

Authors:

Amir M. Ben-Amram,

Holger PetersenAuthors Info & Claims

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

Pages 780 - 786

https://doi.org/10.1145/301250.301450

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

Amir M. Ben-Amram and Zvi Ga/il. On pointers versus addresses. Journal of the A CM, 39:617-648, 1992.

Digital Library

Google Scholar

[2]

Zvi Galil and Joel Seiferas. Time-space-optimal string matching. Journal of Computer and System Sciences, 26:280-294, 1983.

Crossref

Google Scholar

[3]

Neff D. Jones. Computability and Complexity From a Programming Perspective. MIT Press, Cambridge, Mass., London, England, 1997.

Digital Library

Google Scholar

[4]

Nell D. Jones. Must fast pattern marchers be impure? Note distributed during Dagstuhl Seminar 9823 "Programs: Improvements, Complexity, and Meanings", June 8-12, 1998.

Google Scholar

[5]

Donald E. Knuth, James H. Morris, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6:323-350, 1977.

Digital Library

Google Scholar

[6]

Ming Li and Paul Vitinyi. An Introduction to Kolmogorov Complexity and its Applications. Springer, Berlin-Heidelberg-New York, 1993.

Digital Library

Google Scholar

[7]

Friedhelm Meyer auf der Heide. On genuinely time bounded computations. Proc. 6th Syrup. on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science 349, 1-16. Springer-Verlag, 1989.

Digital Library

Google Scholar

[8]

Nicholas Pippenger. Pure versus impure Lisp. A CM Transactions on Programming Languages and Systems, 19:223-238, 1997.

Digital Library

Google Scholar

Cited By

View all

Dvir ATa VErlich SButtyan L(2018)STWSN: A novel secure distributed transport protocol for wireless sensor networksInternational Journal of Communication Systems10.1002/dac.382731:18Online publication date: 21-Oct-2018
https://doi.org/10.1002/dac.3827
Bradford PRay D(2007)Using Digital Chains of Custody on Constrained Devices to Verify Evidence2007 IEEE Intelligence and Security Informatics10.1109/ISI.2007.379522(8-15)Online publication date: May-2007
https://doi.org/10.1109/ISI.2007.379522
Matias YPorat E(2007)Efficient pebbling for list traversal synopses with application to program rollbackTheoretical Computer Science10.1016/j.tcs.2007.02.048379:3(418-436)Online publication date: 10-Jul-2007
https://dl.acm.org/doi/10.1016/j.tcs.2007.02.048
Show More Cited By

Index Terms

Backing up in singly linked lists
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Linked lists
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching

Recommendations

Backing up in singly linked lists

We show how to reduce the time overhead for implementing two-way movement on a singly linked list to O(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 ...
A protocol for piggy-backing on Markov based wavelength reservation in WDM optical networks

During lightpath establishment in WDM optical networks, two important steps, other than routing, are: wavelength selection and wavelength reservation. If two or more lightpaths select the same wavelength, wavelength collision occurs. The basic reason ...
Internet Password Organizer: Password Reminder Book - Alphabetical Organizer Journal Notebook - 5x8 With 110 Pages Vol.5 Password Book

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

May 1999

790 pages

ISBN:1581130678

DOI:10.1145/301250

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC99

Sponsor:

SIGACT

STOC99: ACM Symposium on Theory of Computing

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
396
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)12

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dvir ATa VErlich SButtyan L(2018)STWSN: A novel secure distributed transport protocol for wireless sensor networksInternational Journal of Communication Systems10.1002/dac.382731:18Online publication date: 21-Oct-2018
https://doi.org/10.1002/dac.3827
Bradford PRay D(2007)Using Digital Chains of Custody on Constrained Devices to Verify Evidence2007 IEEE Intelligence and Security Informatics10.1109/ISI.2007.379522(8-15)Online publication date: May-2007
https://doi.org/10.1109/ISI.2007.379522
Matias YPorat E(2007)Efficient pebbling for list traversal synopses with application to program rollbackTheoretical Computer Science10.1016/j.tcs.2007.02.048379:3(418-436)Online publication date: 10-Jul-2007
https://dl.acm.org/doi/10.1016/j.tcs.2007.02.048
Matias YPorat E(2003)Efficient pebbling for list traversal synopsesProceedings of the 30th international conference on Automata, languages and programming10.5555/1759210.1759299(918-928)Online publication date: 30-Jun-2003
https://dl.acm.org/doi/10.5555/1759210.1759299
Matias YPorat E(2003)Efficient Pebbling for List Traversal SynopsesAutomata, Languages and Programming10.1007/3-540-45061-0_71(918-928)Online publication date: 18-Jun-2003
https://doi.org/10.1007/3-540-45061-0_71

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Backing up in singly linked lists

A protocol for piggy-backing on Markov based wavelength reservation in WDM optical networks

Internet Password Organizer: Password Reminder Book - Alphabetical Organizer Journal Notebook - 5x8 With 110 Pages Vol.5 Password Book