Vincent Bouchitte, Roland Jegou, and Jean-Xavier Rampon, On-line recognition of interval orders, IRISA (Institute de Recherche en Informatique et Systemes Aleatoires), Publication No. 751, July 1993.

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 ordering 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 There exist linear-time algorithms for checking this consistency, but these algorithms are off-line, i.e., they require that the entire data is known before they can start working. In the paper under review, an on-line 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).