Tree Pattern Minimisation

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

Uniwersytet Warszawski

Termin

25 lutego 2015 14:15

Pokój

p. 5870

Tytuł w języku angielskim

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

Seminarium

Seminarium „Teoria automatów”

---

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.

---