Thumbnail
Access Restriction
Subscribed

Author Ben-Amram, Amir M. ♦ Petersen, Holger
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Incompressibility ♦ String matching ♦ Two way automata
Abstract 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 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 ε. 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 4
Page Count 25
Starting Page 681
Ending Page 705


Open content in new tab

   Open content in new tab
Source: ACM Digital Library