Title: Streaming algorithms for context-free language recognition

Speaker: Michael Crouch, UMass Amherst

Abstract: 
We will review existing work on streaming algorithms for recognizing
formal languages.  Recent papers have found a small-space two-pass
algorithm for the Dyck language of balanced parentheses, an important
deterministic context-free language with applications to XML parsing,
with the odd feature that the second pass must be in reverse order.
Followup papers have shown that the reverse-order pass is necessary,
and have studied restricted subclasses of CFL with one-pass
algorithms.  We will conclude by discussing our progress towards
characterizing traditional language-theoretic problems in terms of
their streaming-space requirements.