Gore, Rajeev; Nguyen, Linh Anh
The description logic SHI extends the basic description logic ALC with transitive roles, role hierarchies and inverse roles. The known tableau-based decision procedure  for SHI exhibit (at least) NEXP-TIME behaviour even though SHI is known to be EXPTIME-complete. The automata-based algorithms for SHI often yield optimal worst-case complexity results, but do not behave well in practice since good optimisations for them have yet to be found. We extend our method for global caching in ALC to...[Show more]
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.