The HOM Problem is EXPTIME-Complete.
Carles CreusAdrià GascónGuillem GodoyLander RamosPublished in: SIAM J. Comput. (2016)
Keyphrases
- exptime complete
- description logics
- data complexity
- expressive power
- pspace complete
- expressive description logics
- np complete
- transitive closure
- decision problems
- tree automata
- query containment
- query answering
- model checking
- knowledge base
- satisfiability problem
- knowledge compilation
- reasoning tasks
- query language
- query evaluation
- first order logic
- knowledge representation
- query complexity
- conjunctive queries
- domain independent
- relational databases