@InProceedings{RS82a,
replaced-by = { RS82c },
author = { Ronald L. Rivest and Adi Shamir },
title = { How to reuse a ``write-once'' memory (Preliminary version) },
doi = { 10.1145/800070.802182 },
acmid = { 802182 },
pages = { 105--113 },
acm = { 09698 },
booktitle = { Proceedings of the fourteenth annual ACM symposium on Theory of Computing },
isbn = { 0-89791-070-2 },
publisher = { ACM },
date = { 1982-05 },
OPTyear = { 1982 },
OPTmonth = { May 5--7, },
OPTeditor = { Harry R. Lewis },
eventtitle = { STOC'82 },
eventdate = { 1982-05-05/1982-05-07 },
venue = { San Francisco, California },
abstract = {
Storage media such as digital optical disks, PROMS, or
paper tape consist of a number of ``write-once'' bit positions (wits);
each wit initially contains a ``0'' that may later be
irreversibly overwritten with a ``1''. We demonstrate that
such ``write-once memories'' (woms) can be ``rewritten'' to
a surprising degree. For example, only 3 wits suffice to represent
any 2-bit value in a way that can be later update 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. $kt$ when writing a $k$-bit value $t$ times)
of up to $n \log (n)$ bits.
},
}