Streaming and Circuit Complexity

In this talk, I will present a connection between the streaming complexity and the circuit complexity of regular languages through a notion of streaming by block. This result provides tight constructions of "streaming boolean circuits" computing an automaton, thanks to some classical and recent results on the circuit complexity of regular languages. As an illustration of this method, I will present an application to schema validation in streaming for XML documents.