Validating XML documents in the streaming model with external memory
Christian Konrad, Frédéric Magniez · 2012
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 lower bound. There are XML documents and DTDs for which p-pass streaming algorithms require Ω(N/p) space.