Skip navigation
Skip navigation

EXPTIME tableaux with global caching for description logics with transitive roles, inverse roles and role hierarchies

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 [9] 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]

CollectionsANU Research Publications
Date published: 2007
Type: Conference paper
Source: Proceedings of TABLEAUX 2007


File Description SizeFormat Image
01_Gore_EXPTIME_tableaux_with_global_2007.pdf392.22 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator