RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
1 декабря 2015 г. 18:30, г. Москва, ГЗ МГУ, ауд. 16-04
 


Оценки длин преобразований запросов к снабженным логической теорией базам данных

В. В. Подольскийab

a Национальный исследовательский университет "Высшая школа экономики", г. Москва
b Математический институт им. В.А. Стеклова Российской академии наук, г. Москва

Количество просмотров:
Эта страница:26

Аннотация: В докладе будет рассказано о ряде результатов докладчика по приложению теории сложности булевых схем к так называемым базам данных с онтологическим доступом. На элементах такой базы данных задаются предикаты, а также некоторая логическая теория первого порядка. Запросом к такой базе данных является формула логики первого порядка, а ответом на запрос является набор элементов базы данных, удовлетворяющий этой формуле. Стандартным подходом к ответу на запрос является преобразование данного запроса к базе данных в таком виде, чтобы для поиска ответа на запрос не нужно было обращаться к логической теории, сопровождающей базу данных. В докладе будет обсуждаться вопрос о том, насколько увеличивается длина запроса при таком преобразовании. Будет рассказано о ряде верхних и нижних оценок этой величины при различных ограничениях на виды рассматриваемых логических теорий, запросов и преобразований запросов. Для получения этих оценок используются классические результаты из теории сложности булевых схем.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018