Nie jesteś zalogowany |
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.
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.
