On the complexity of (restricted) AlCIr | Zendy

Milenko Mosurović | Zendy; Michael Zakharyaschev | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the complexity of (restricted) AlCIr

Author(s) -

Milenko Mosurović,

Michael Zakharyaschev

Publication year - 2014

Publication title -

publications de l institut mathematique

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.246

H-Index - 17

eISSN - 1820-7405

pISSN - 0350-1302

DOI - 10.2298/pim1409133m

Subject(s) - exptime , satisfiability , axiom , mathematics , pspace , boolean satisfiability problem , discrete mathematics , combinatorics , computer science , computational complexity theory , algorithm , geometry

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research