Publications: Abstract

# Abstract Storage Devices

## Robert Koenig and Ueli Maurer and Stefano Tessaro

 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.