joint work with Wim Martens, Matthias Niewerth and Paweł Parys

Speaker(s)

Wojciech Czerwiński

Affiliation

Uniwersytet Warszawski

Date

Feb. 25, 2015, 2:15 p.m.

Room

room 5870

Title in Polish

Tree Pattern Minimisation

Seminar

Seminar Automata Theory

---

I will consider the problem of minimising tree pattern queries. I will show you the example, which contradicted the long standing conjecture that minimality is the same as nonredundancy. Then I will present how this leads to the \Pi^2_P-completeness of the minimisation problem.

---