Characterizing history independent data structures

被引：18

作者：

Hartline, JD

Hong, ES

Mohr, AE

Pentney, WR

Rocke, EC

机构：

[1] Microsoft Res, Mountain View, CA 94043 USA

[2] Univ Washington, Tacoma, WA 98402 USA

[3] SUNY Stony Brook, Dept Comp Sci, Stony Brook, NY 11794 USA

[4] Univ Washington, Dept Comp Sci, Seattle, WA 98195 USA

来源：

ALGORITHMICA | 2005年 / 42卷 / 01期

关键词：

data structures; history independence; Markov chains; algorithms;

D O I：

10.1007/s00453-004-1140-z

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We consider history independent data structures as proposed for study by Naor and Teague [3]. In a history independent data structure, nothing can be learned from the memory 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 provide a natural alternative definition of strong history independence that is less restrictive than [3] 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.

引用

页码：57 / 74

页数：18