Fully Persistent Lists with Catenation

James R. Driscoll; Daniel D.K. Sleator; Robert E. Tarjan

doi:10.1145/185675.185791

Fully Persistent Lists with Catenation

James R. Driscoll, Daniel D.K. Sleator, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O1994 time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.

Original language	English (US)
Pages (from-to)	943-959
Number of pages	17
Journal	Journal of the ACM (JACM)
Volume	41
Issue number	5
DOIs	https://doi.org/10.1145/185675.185791
State	Published - Jan 9 1994

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Keywords

LISP
amortization
catenation
concatenation
data structures
functional programming
list
queue
stack

Access to Document

10.1145/185675.185791

Cite this

@article{85c262bca60d40db854f06526c60c859,

title = "Fully Persistent Lists with Catenation",

abstract = "This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O1994 time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.",

keywords = "LISP, amortization, catenation, concatenation, data structures, functional programming, list, queue, stack",

author = "Driscoll, {James R.} and Sleator, {Daniel D.K.} and Tarjan, {Robert E.}",

year = "1994",

month = jan,

day = "9",

doi = "10.1145/185675.185791",

language = "English (US)",

volume = "41",

pages = "943--959",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "5",

}

TY - JOUR

T1 - Fully Persistent Lists with Catenation

AU - Driscoll, James R.

AU - Sleator, Daniel D.K.

AU - Tarjan, Robert E.

PY - 1994/1/9

Y1 - 1994/1/9

N2 - This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O1994 time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.

AB - This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O1994 time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.

KW - LISP

KW - amortization

KW - catenation

KW - concatenation

KW - data structures

KW - functional programming

KW - list

KW - queue

KW - stack

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

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

U2 - 10.1145/185675.185791

DO - 10.1145/185675.185791

M3 - Article

AN - SCOPUS:0028513481

SN - 0004-5411

VL - 41

SP - 943

EP - 959

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 5

ER -

Fully Persistent Lists with Catenation

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this