@Article{RS82c,
author = { Ronald L. Rivest and Adi Shamir },
title = { How to reuse a ``write-once'' memory },
journal = { Information and Control },
issn = { 0019-9958 },
OPTyear = { 1982 },
date = { 1982-10 },
issue = { October-December },
volume = { 55 },
number = { 1--3 },
pages = { 1--19 },
doi = { 10.1016/S0019-9958(82)90344-8 },
url = { http://www.sciencedirect.com/science/article/pii/S0019995882903448 },
publisher = { Academic Press },
abstract = {
Storage media such as digital optical disks, {PROMS},
or paper tape consist of a number of ``write-once'' bit
positions (\emph{wits}); each wit initially contains a
``0'' that may later be \emph{irreversibly} overwritten
with a ``1.'' It is demonstrated that such ``write-once
memories (\emph{woms}) can be ``rewritten'' to a surprising
degree. For eacmple, only 3 wits suffice to represent any
2-bit value in a way that can later be updated to represent any
other 2-bit value. For large $k$, $1.29\ldots\cdot k$ wits
suffice to represent a $k$-bit value in a way that can be
similarly updated. Most surprising, allowing $t$ writes of a
$k$-bit value requires only $t+o(t)$ wits, for any fixed $k$.
For fixed $t$, approximately $k\cdot t/\log(t)$ wits are
required as $k\rightarrow \infty$. An $n$-wite {WOM} is
shown to have a ``capacity'' (i.e., $k\cdot t$ when writing
a $k$-bit value $t$ times) of up to $n\cdot\log(n)$ bits.
},
}