CrossRef 2014

On the complexity of (restricted) AlCIr

Milenko Mosurovic Michael Zakharyaschev

Abstrak

We consider a new description logic ALCIr that extends ALCI with role inclusion axioms of the form R ? QR1 . . .Rm satisfying a certain regularity condition. We prove that concept satisfiability with respect to RBoxes in this logic is ExpTime-hard. We then define a restriction ALCIr? of ALCIr and show that concept satisfiability with respect to RBoxes in ALCIr? is PSpace-complete.

Penulis (2)

Milenko Mosurovic

Michael Zakharyaschev

Format Sitasi

APA MLA BibTeX

Mosurovic, M., Zakharyaschev, M. (2014). On the complexity of (restricted) AlCIr. https://doi.org/10.2298/pim1409133m

Akses Cepat

PDF tidak tersedia langsung

Cek di sumber asli →

Lihat di Sumber doi.org/10.2298/pim1409133m

Informasi Jurnal

Tahun Terbit: 2014
Bahasa: en
Sumber Database: CrossRef
DOI: 10.2298/pim1409133m
Akses: Terbatas