ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2009, ТОМ 15, ВЫПУСК 5, СТР. 49-61

Достаточные условия эффективной трансляции локально генерических запросов

С. М. Дудаков

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

Данная работа является продолжением исследований по теории языков запросов первого порядка к базам данных. Ранее было установлено, что во многих разрешимых теориях имеет место трансляционная теорема: каждый локально генерический запрос эквивалентен некоторому ограниченному, но вопрос о возможности эффективного нахождения этого запроса почти не исследовался. Используя полученные нами ранее результаты, мы предлагаем метод эффективного нахождения этих запросов для широкого класса теорий, который включает арифметику Пресбургера и теорию действительных чисел.

Полнотекстовая версия статьи в формате PDF (148 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k09/k095/k09504h.htm
Изменения вносились 8 октября 2010 г.