RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
Video Library
Archive
Most viewed videos

Search
RSS
New in collection





You may need the following programs to see the files






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

Number of views:
This page:381
Video files:139

Agi Kurucz, Frank Wolter, Michael Zakharyaschev


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

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).

Language: English

SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017