Abstract Storage Devices

Robert Koenig, Ueli Maurer, and Stefano Tessaro

Theory and Practice of Computer Science — SOFSEM 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5404, pp. 341–352, Jan 2009.

The purpose of this paper is to initiate the study of a combinatorial abstraction, called abstract storage device (ASD), which models deterministic storage devices with the property that only partial information about the state can be read, but that there is a degree of freedom as to which partial information should be retrieved.

We study several combinatorial problems related to ASD's, including reducibility among ASD's, which we prove to be $\mathcal{NP}$-complete, and the factorization of ASD's. The factorization into binary-output devices is proved to be unique.

BibTeX Citation

@inproceedings{KoMaTe09,
    author       = {Robert Koenig and Ueli Maurer and Stefano Tessaro},
    title        = {Abstract Storage Devices},
    booktitle    = {Theory and Practice of Computer Science --- SOFSEM 2009},
    pages        = {341--352},
    series       = {Lecture Notes in Computer Science},
    volume       = {5404},
    year         = {2009},
    month        = {1},
    publisher    = {Springer-Verlag},
}