Simple confluently persistent catenable lists

Haim Kaplan; Chris Okasaki; Robert E. Tarjan

doi:10.1007/BFb0054360

Simple confluently persistent catenable lists

Haim Kaplan, Chris Okasaki, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive-each operation produces a new list incorporating the change while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues with catenation that supports all deque operations in constant amortized time.

Original language	English (US)
Title of host publication	Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings
Editors	Stefan Arnborg, Lars Ivansson
Publisher	Springer Verlag
Pages	119-130
Number of pages	12
ISBN (Print)	3540646825, 9783540646822
DOIs	https://doi.org/10.1007/BFb0054360
State	Published - 1998
Event	6th Scandinavian Workshop on Algorithm Theory, SWAT 1998 - Stockholm, Sweden Duration: Jul 8 1998 → Jul 10 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1432
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th Scandinavian Workshop on Algorithm Theory, SWAT 1998
Country/Territory	Sweden
City	Stockholm
Period	7/8/98 → 7/10/98

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/BFb0054360

Cite this

Kaplan, H., Okasaki, C., & Tarjan, R. E. (1998). Simple confluently persistent catenable lists. In S. Arnborg, & L. Ivansson (Eds.), Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 119-130). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1432). Springer Verlag. https://doi.org/10.1007/BFb0054360

Kaplan, Haim ; Okasaki, Chris ; Tarjan, Robert E. / Simple confluently persistent catenable lists. Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. editor / Stefan Arnborg ; Lars Ivansson. Springer Verlag, 1998. pp. 119-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0f4a01f9e2e149ef8fe090b4d71101c3,

title = "Simple confluently persistent catenable lists",

abstract = "We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive-each operation produces a new list incorporating the change while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues with catenation that supports all deque operations in constant amortized time.",

author = "Haim Kaplan and Chris Okasaki and Tarjan, {Robert E.}",

year = "1998",

doi = "10.1007/BFb0054360",

language = "English (US)",

isbn = "3540646825",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "119--130",

editor = "Stefan Arnborg and Lars Ivansson",

booktitle = "Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings",

address = "Germany",

}

Kaplan, H, Okasaki, C & Tarjan, RE 1998, Simple confluently persistent catenable lists. in S Arnborg & L Ivansson (eds), Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1432, Springer Verlag, pp. 119-130, 6th Scandinavian Workshop on Algorithm Theory, SWAT 1998, Stockholm, Sweden, 7/8/98. https://doi.org/10.1007/BFb0054360

Simple confluently persistent catenable lists. / Kaplan, Haim; Okasaki, Chris; Tarjan, Robert E.
Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. ed. / Stefan Arnborg; Lars Ivansson. Springer Verlag, 1998. p. 119-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1432).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Simple confluently persistent catenable lists

AU - Kaplan, Haim

AU - Okasaki, Chris

AU - Tarjan, Robert E.

PY - 1998

Y1 - 1998

N2 - We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive-each operation produces a new list incorporating the change while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues with catenation that supports all deque operations in constant amortized time.

AB - We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive-each operation produces a new list incorporating the change while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues with catenation that supports all deque operations in constant amortized time.

UR - http://www.scopus.com/inward/record.url?scp=84957617846&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957617846&partnerID=8YFLogxK

U2 - 10.1007/BFb0054360

DO - 10.1007/BFb0054360

M3 - Conference contribution

AN - SCOPUS:84957617846

SN - 3540646825

SN - 9783540646822

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 119

EP - 130

BT - Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Arnborg, Stefan

A2 - Ivansson, Lars

PB - Springer Verlag

T2 - 6th Scandinavian Workshop on Algorithm Theory, SWAT 1998

Y2 - 8 July 1998 through 10 July 1998

ER -

Kaplan H, Okasaki C, Tarjan RE. Simple confluently persistent catenable lists. In Arnborg S, Ivansson L, editors, Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. Springer Verlag. 1998. p. 119-130. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0054360

Simple confluently persistent catenable lists

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this