Solving datalog containment via bounded cliquewidth

Prelegent(ci)

Adam Witkowski

Afiliacja

Uniwersytet Warszawski

Termin

29 kwietnia 2015 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Containment of monadic datalog over data trees is known to be undecidable in general but decidable
for two fragments: downward programs and linear child-only ones.
I will describe a method for deciding the containment
by bounding clique-width of possible counter-examples to the containment.
This approach allowed us to unify the proofs for both those fragments
and to obtain tight complexity in the case of linear child-only programs.

---