Validating XML Documents in the Streaming Model with External Memory

Christian Konrad, Frederic Magniez

We study the problem of validating XML documents of size $N$ against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lowe…