Videolibrary
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 Video Library Archive Most viewed videos Search RSS New in collection

The eighth International ñonference "Advances in Modal Logic" (AiML 2010)
August 24, 2010 10:50, Moscow

Islands of tractability for relational constraints: towards dichotomy results for the description logic $\mathcal{EL}$

Agi Kurucz, Frank Wolter, Michael Zakharyaschev
 Video records: Windows Media 232.3 Mb Flash Video 414.1 Mb MP4 414.1 Mb

Abstract: $\mathcal{EL}$ is a tractable description logic serving as the logical underpinning of large-scale ontologies. We launch a systematic investigation of the boundary between tractable and intractable reasoning in $\mathcal{EL}$ under relational constraints. For example, we show that there are (modulo equivalence) exactly 3 universal constraints on a transitive and reflexive relation under which reasoning is tractable: being a singleton set, an equivalence relation, or the empty constraint. We prove a number of results of this type and discuss a spectrum of open problems including generalisations to the algebraic semantics for $\mathcal{EL}$ (semi-lattices with monotone operators).