Solving datalog containment via bounded cliquewidth

Speaker(s)

Adam Witkowski

Affiliation

Uniwersytet Warszawski

Date

April 29, 2015, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---