Description Logics and complexity theory #2
Description
Ontologies are based in fragments of first-order logic that are decidable. Given that they are decidable, an algorithm will halt (eventually) on an input that follows that DL. Most ontology editors have the ability to execute a reasoner that eventually halts, but are there good estimates on the time complexity it takes for those reasoners to run? Are there any resources that you can recommend related to the time complexities of reasoning over ontologies and the trade-offs between different reasoner implementations?