Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Восьмая Международная конференция серии «Advances in Modal Logic» (AiML 2010)
24 августа 2010 г. 10:50, г. Москва
 


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

Agi Kurucz, Frank Wolter, Michael Zakharyaschev
Видеозаписи:
Windows Media 232.3 Mb
Flash Video 414.1 Mb
MP4 260.3 Mb

Количество просмотров:
Эта страница:635
Видеофайлы:208

Agi Kurucz, Frank Wolter, Michael Zakharyaschev



Аннотация: $\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).

Язык доклада: английский
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024