Michael Benedikt

Logic on Streams

Query languages on strings and trees that have the same expressiveness
may still vary significantly in the complexity of model-checking. This
is true when we consider traditional in-memory model-checking, but also
if we consider computational models that require single-pass access
to the data (roughly speaking "streaming computation models"). We consider
this issue for first-order query languages on trees, looking at two
questions: which queries can be performed in a single pass, and which queries
can be efficiently translated into single-pass processors.  This talk
includes joint work with Alan Jeffrey of Bell Labs and Clemens Ley of Oxford.