Metadata only
Date
2009Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
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. Show more
Publication status
publishedExternal links
Editor
Book title
SOFSEM 2009: Theory and Practice of Computer ScienceJournal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerEvent
Subject
Discrete Structures; Storage Devices; NP-Completeness; Computational Complexity; FactorizationsOrganisational unit
03338 - Maurer, Ueli / Maurer, Ueli
More
Show all metadata
ETH Bibliography
yes
Altmetrics