Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Abstract Storage Devices
verfasst von : Robert König, Ueli Maurer, Stefano Tessaro
Erschienen in: SOFSEM 2009: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal{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.