Schema validation via streaming circuits

Prelegent(ci)

Filip Murlak

Afiliacja

Uniwersytet Warszawski

Termin

1 czerwca 2016 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Charles Paperman and Michal Pilipczuk

Seminarium

Seminarium „Teoria automatów”

---

I will talk about recognizing regular tree languages in a model where
the input is streamed to the recognizer as a sequence of tags
(possibly representing a tree in the usual XML encoding). It is known
that a regular tree language can be recognized in this model if and
only if the depth of all trees in the language is bounded; the
algorithm amounts to running a finite automaton obtained from the tree
automaton. We shall consider a variant of the streaming model in which
the stream is read in blocks of fixed size (rather than
letter-by-letter) and explore possibilities of parallelizing
computation over each block. This is going to be a "theoretical
engineering" talk: I will not prove any deep theorems, but will show
how existing knowledge from circuit complexity could be used in
practice.

---