TY - GEN
T1 - Abstract storage devices
AU - Kónig, Robert
AU - Maurer, Ueli
AU - Tessaro, Stefano
N1 - Funding Information:
This research was partially supported by the Swiss National Science Foundation (SNF), project no. 200020-113700/1.
PY - 2009
Y1 - 2009
N2 - The purpose of this paper is to initiate the study of a combinatorial straction, 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 nformation 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.
AB - The purpose of this paper is to initiate the study of a combinatorial straction, 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 nformation 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.
UR - http://www.scopus.com/inward/record.url?scp=67650706267&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-95891-8_32
DO - 10.1007/978-3-540-95891-8_32
M3 - Conference contribution
AN - SCOPUS:67650706267
SN - 3540958908
SN - 9783540958901
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 341
EP - 352
BT - SOFSEM 2009
T2 - 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009
Y2 - 24 January 2009 through 30 January 2009
ER -