Characterizing history independent data structures

Jason D. Hartline; Edwin S. Hong; Alexander E. Mohr; William R. Pentney; Emily C. Rocke

doi:10.1007/3-540-36136-7_21

Characterizing history independent data structures

Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, Emily C. Rocke

Computer Science

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

7 Scopus citations

Abstract

We consider history independent data structures as proposed for study by Teague and Naor [3]. In a history independent data structure, nothing can be learned from the representation of the data structure except for what is available from the abstract data structure. We show that for the most part, strong history independent data structures have canonical representations. We also provide a natural less restrictive definition of strong history independence and characterize how it restricts allowable representations. We also give a general formula for creating dynamically resizing history independent data structures and give a related impossibility result.

Original language	English
Title of host publication	Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Pages	229-240
Number of pages	12
Volume	2518 LNCS
DOIs	https://doi.org/10.1007/3-540-36136-7_21
State	Published - 2002
Event	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada Duration: Nov 21 2002 → Nov 23 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2518 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Country/Territory	Canada
City	Vancouver, BC
Period	11/21/02 → 11/23/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36136-7_21

Cite this

Hartline, J. D., Hong, E. S., Mohr, A. E., Pentney, W. R., & Rocke, E. C. (2002). Characterizing history independent data structures. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings (Vol. 2518 LNCS, pp. 229-240). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS). https://doi.org/10.1007/3-540-36136-7_21

Hartline, Jason D. ; Hong, Edwin S. ; Mohr, Alexander E. et al. / Characterizing history independent data structures. Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Vol. 2518 LNCS 2002. pp. 229-240 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{17602dcfc22c453bb26f85700c99b576,

title = "Characterizing history independent data structures",

abstract = "We consider history independent data structures as proposed for study by Teague and Naor [3]. In a history independent data structure, nothing can be learned from the representation of the data structure except for what is available from the abstract data structure. We show that for the most part, strong history independent data structures have canonical representations. We also provide a natural less restrictive definition of strong history independence and characterize how it restricts allowable representations. We also give a general formula for creating dynamically resizing history independent data structures and give a related impossibility result.",

author = "Hartline, {Jason D.} and Hong, {Edwin S.} and Mohr, {Alexander E.} and Pentney, {William R.} and Rocke, {Emily C.}",

year = "2002",

doi = "10.1007/3-540-36136-7_21",

language = "English",

isbn = "3540001425",

volume = "2518 LNCS",

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

pages = "229--240",

booktitle = "Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings",

note = "13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 ; Conference date: 21-11-2002 Through 23-11-2002",

}

Hartline, JD, Hong, ES, Mohr, AE, Pentney, WR & Rocke, EC 2002, Characterizing history independent data structures. in Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. vol. 2518 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2518 LNCS, pp. 229-240, 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, BC, Canada, 11/21/02. https://doi.org/10.1007/3-540-36136-7_21

Characterizing history independent data structures. / Hartline, Jason D.; Hong, Edwin S.; Mohr, Alexander E. et al.
Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Vol. 2518 LNCS 2002. p. 229-240 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS).

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

TY - GEN

T1 - Characterizing history independent data structures

AU - Hartline, Jason D.

AU - Hong, Edwin S.

AU - Mohr, Alexander E.

AU - Pentney, William R.

AU - Rocke, Emily C.

PY - 2002

Y1 - 2002

N2 - We consider history independent data structures as proposed for study by Teague and Naor [3]. In a history independent data structure, nothing can be learned from the representation of the data structure except for what is available from the abstract data structure. We show that for the most part, strong history independent data structures have canonical representations. We also provide a natural less restrictive definition of strong history independence and characterize how it restricts allowable representations. We also give a general formula for creating dynamically resizing history independent data structures and give a related impossibility result.

AB - We consider history independent data structures as proposed for study by Teague and Naor [3]. In a history independent data structure, nothing can be learned from the representation of the data structure except for what is available from the abstract data structure. We show that for the most part, strong history independent data structures have canonical representations. We also provide a natural less restrictive definition of strong history independence and characterize how it restricts allowable representations. We also give a general formula for creating dynamically resizing history independent data structures and give a related impossibility result.

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

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

U2 - 10.1007/3-540-36136-7_21

DO - 10.1007/3-540-36136-7_21

M3 - Conference contribution

AN - SCOPUS:35248817365

SN - 3540001425

SN - 9783540001423

VL - 2518 LNCS

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

SP - 229

EP - 240

BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings

T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002

Y2 - 21 November 2002 through 23 November 2002

ER -

Hartline JD, Hong ES, Mohr AE, Pentney WR, Rocke EC. Characterizing history independent data structures. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Vol. 2518 LNCS. 2002. p. 229-240. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36136-7_21

Characterizing history independent data structures

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this