Ground reducibility is EXPTIME-complete.
Hubert ComonFlorent JacquemardPublished in: Inf. Comput. (2003)
Keyphrases
- exptime complete
- description logics
- expressive power
- data complexity
- pspace complete
- expressive description logics
- np complete
- transitive closure
- model checking
- decision problems
- satisfiability problem
- query evaluation
- query containment
- knowledge representation
- first order logic
- tree automata
- knowledge base
- incomplete information
- query answering
- reasoning tasks
- artificial intelligence
- matching algorithm
- data warehouse
- objective function