joint work with Charles Paperman and Michal Pilipczuk

Speaker(s)

Filip Murlak

Affiliation

Uniwersytet Warszawski

Date

June 1, 2016, 2:15 p.m.

Room

room 5870

Title in Polish

Schema validation via streaming circuits

Seminar

Seminar Automata Theory

---

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.

---