Published 2009
| Submitted
Book Section - Chapter
Open
Abstract Storage Devices
Abstract
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 combinatorial problems related to ASD's, including reducibility among ASD's, which is proved to be NP-complete, and the factorization of ASD's. In particular, we prove that the factorization into binary-output ASD's (if it exists) is unique.
Additional Information
© 2009 Springer-Verlag Berlin Heidelberg. This research was partially supported by the Swiss National Science Foundation (SNF), project no. 200020-113700/1. Work done while at ETH Zurich. We would like to thank Thomas Holenstein and Renato Renner for helpful discussions.Attached Files
Submitted - 0706.2746.pdf
Files
0706.2746.pdf
Files
(276.0 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:30f3c1d3ef91b4aacf68def212eca2fe
|
276.0 kB | Preview Download |
Additional details
- Eprint ID
- 88805
- Resolver ID
- CaltechAUTHORS:20180814-155026419
- 200020-113700/1
- Swiss National Science Foundation (SNSF)
- Created
-
2018-08-15Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 5404