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

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






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


On the size of shortest modal descriptions

Santiago Figueira, Daniel Gorín
Видеозаписи:
Windows Media 213.3 Mb
Flash Video 386.9 Mb
MP4 243.7 Mb

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

Santiago Figueira, Daniel Gorín



Аннотация: We address the problems of separation and description in some fragments of modal logics. The former consists in finding a formula that is true in some given subset of the domain and false in another. The latter is a special case when one separates a singleton from the rest. We are interested in the shortest size of both separations and descriptions. This is motivated by applications in computational linguistics. Lower bounds are given by considering the minimum size of Spoiler's strategies in the classical Ehrenfeucht-Fraïssé game. This allows us to show that the size of such formulas is not polynomially bounded (with respect to the size of the finite input model). Upper bounds for these problems are also studied. Finally we give a fine hierarchy of succinctness for separation over the studied logics.

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