Vincent Bouchitte, Roland Jegou, and Jean-Xavier Rampon,
<I> On-line recognition of interval orders</I>, IRISA (Institute de
Recherche en Informatique et Systemes Aleatoires), Publication No.
751, July 1993. 
<P>
Suppose that for a given set of events $e_1,\ldots,e_n$, an expert
describes which event precedes which (we will denote this precedence
relation by $e_i<e_j$). Is this description consistent? In
mathematical terms, is $<$ an <I> ordering</I> relation, and, if it is,
is it an {\it interval order}, i.e., do there exist intervals ${\bf
a}_1=[a^-_1,a^+_1],\ldots, {\bf a}_n=[a^-_n,a^+_n]$ such that
$a^+_i<a^-_j$ iff $e_i<e_j$? 
<P>
There exist linear-time algorithms for checking this consistency, but
these algorithms are <I> off-line</I>, i.e., they require that the
entire data is known before they can start working. In the paper under
review, an <I> on-line</I> algorithm is presented for checking
consistency. In other words, if we have an interval order, and we add
a new event $e$, with a list of events that precede $e$ and a list of
events that are preceded by $e$, then this algorithm checks whether
the resulting relation is an interval order 
in time that is linear in the size of
the added data (i.e., in the size of these two lists).