An ExpSpace Tableau-based Algorithm for SHOIQ

Abstract : In this work, we propose an ExpSpace tableau-based algorithm for deciding consistency of a knowledge base in the description logic SHOIQ. The construction of this algorithm is founded on the standard tableau-based method for SHOIQ and the technique used for designing a NExpTime algorithm for the two-variable fragment of first-order logic with counting quantifiers C^2.
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00570161
Contributor : Chan Le Duc <>
Submitted on : Saturday, June 2, 2012 - 11:38:07 AM
Last modification on : Tuesday, May 22, 2018 - 8:40:06 PM
Long-term archiving on : Thursday, December 15, 2016 - 10:42:04 AM

File

optimal-shoiq.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00570161, version 3

Citation

Chan Le Duc, Myriam Lamolle, Olivier Curé. An ExpSpace Tableau-based Algorithm for SHOIQ. [Research Report] 2012, pp.36. ⟨inria-00570161v3⟩

Share

Metrics

Record views

425

Files downloads

269