Nie jesteś zalogowany |
Between tree patterns and conjunctive queries: computational complexity of boolean combinations of patterns.
- Prelegent(ci)
- Marcin Przybyłko
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 18 lipca 2012 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
In static analysis of patterns, negation causes drastic increase of complexity. When consider patterns that allow both data comparison and negation, undecidability can be reached with simple queries. Even without data, potential complexity is unacceptably high, being 2 EXPTIME-complete in contrast to NP-complete satisfiability of positive queries (Bjorklund, Martens and Schwentick MFCS'08). However, using tree patterns and restricting schema gives hope of achieving relatively low complexity classes.
In
this talk I will consider satisfiability of boolean combinations of patterns, in the presence of a schema, and show how some restrictions on
pattern or schema structure affect the complexity.
