You are not logged in |
Between tree patterns and conjunctive queries: computational complexity of boolean combinations of patterns.
- Speaker(s)
- Marcin Przybyłko
- Affiliation
- Uniwersytet Warszawski
- Date
- July 18, 2012, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
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.
