Complexity of finite-variable fragments M of EXPTIME-complete logics.
Mikhail N. RybakovPublished in: J. Appl. Non Class. Logics (2007)
Keyphrases
- exptime complete
- expressive power
- description logics
- pspace complete
- data complexity
- expressive description logics
- decision problems
- np complete
- number restrictions
- first order logic
- satisfiability problem
- transitive closure
- lower complexity
- query answering
- query language
- inference rules
- computational complexity
- relational algebra
- search algorithm