Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

The complexity of probabilistic EL

Gutierrez Basulto, Victor ORCID:, Jung, Jean Christoph, Lutz, Carsten and Schroder, Lutz 2011. The complexity of probabilistic EL. Presented at: 24th International Workshop on Description Logics, DL 2011, Barcelona, Spain, July 13-16, 2011.

[thumbnail of GuJuLuSchroe-DL11.pdf]
PDF - Presentation
Download (279kB) | Preview


We analyze the complexity of subsumption in probabilistic variants of the description logic EL. In the case where probabilities apply only to concepts, we map out the borderline between tractability and EXPTIME-completeness. One outcome is that any probability value except zero and one leads to intractability in the presence of general TBoxes, while this is not the case for classical TBoxes. In the case where probabilities can also be applied to roles, we show PSPACEcompleteness. This result is (positively) surprising as the best previously known upper bound was 2-EXPTIME and there were reasons to believe in completeness for this class.

Item Type: Conference or Workshop Item (Paper)
Status: Unpublished
Schools: Computer Science & Informatics
Date of First Compliant Deposit: 5 June 2018
Last Modified: 23 Oct 2022 13:52

Citation Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics