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

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






«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
1 декабря 2015 г. 18:30, г. Москва, Математический институт им.В.А.Стеклова РАН
 


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

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

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

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

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

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