models.tex from gzz at Krugle
Show models.tex syntax highlighted
\documentclass{article}
\usepackage{beton}
\usepackage{euler}
\usepackage{bbm}
\begin{document}
\def\seq{\hbox{\rm Seq}}
\def\naturals{\mathbbmss{N}}
This document discusses the models of referential media
presented in the article more formally.
Specifically, we present a formal model for the abstract
referential media model presented in \cite{nelson99xanalogicalneeded},
and the Scrollblock and Random-id content-carrying models
presented in the article. The Page- and PageImage spans do not
deal with the fundamental referential model and do not need
to be discussed in this context.
Define $C$ as a finite set of \emph{characters} $c \in C$.
Define $\seq(X)$ as the class of
finite sequences of elements of type $X$.
\section{Standard text model}
The standard text model handles text as String objects,
representing a region of text.
The class of strings is simply $\seq(C)$.
\section{Basic referential text abstraction}
The fundamental referential text model adds an indirection step:
an abstract ``text universe'' is defined, with the class $P$
of permanent references.
The text universe has two operations:
$\hbox{\rm add}(c : C) : P$ and
$\hbox{\rm get}(p : P) : C$.
However, the crux lies in the definitions of these mapping:
add shall return a \emph{unique} element of $P$ that has never
been returned before by any other invocation of add ever, whereas
the results from get shall naturally not be unique.
In this model, the class of strings is $\seq(P)$, adding
a level of indirection to the ``text universe''.
The important properties of this model are that
the equality of two strings is not defined by their character
values but by their permanent references.
Because class of permanent references $P$ is opaque,
strings shall only be equal if they have been copied
from the same source by some route.
In realistic implementations, the class $P$ has some structure
which is exploited in ... spans ...
\section{Scrollblocks}
The idea of scrollblocks is to make the structure of $P$
explicit: a permanent reference $p$ is the tuple $(b, i)$
where $b$ is ... and $i \in \naturals$ is the offset inside the block.
If content hashes are used ... approximate ...
In realistic implementations, a span is a tuple $(b, i, l)$
which stands for the sequence
$\left( (b, i), (b, i+1) ... (b, i+l-1) \right)$.
\section{RICC referential media}
The RICC (random-id, content-carrying) model of referential media
is approximate: the uniqueness property
of the add operation is obeyed only with an arbitrarily
high probability.
On the other hand, the RICC model has significant advantages
over the more usual models: it is by far the simplest to implement
and adapt to existing programs.
The universe can be implemented statically, requiring no
communication.
A permanent reference $p$ in this model is the tuple $(r, c)$ with
$r \in \naturals$, and $c \in C$.
The number $r$ is generated randomly at the time of the get operation.
In this context, the get operation of the text universe
does not need access to any external data and is simply a projection
to the second member of the tuple:
$\hbox{\rm get}( p ) =
\hbox{\rm get}( (r, c) )
= c$.
In realistic implementations, a single random number is used
for some \emph{sequence} of characters, and indices to that sequence
are attached to the span: a span is a triple $(r, i, s)$
where $i \in N$ is the index and $s \in \seq(C)$.
\end{document}
See more files for this project here