Семантика и анализ сложности алгоритмических проблем динамических систем и языков, использующих логическое программирование

• Автор: Дехтярь, Михаил Иосифович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Тверь
• Количество страниц: 383 с. : ил.

Оглавление
Введение

1 Основные понятия

1.1 Логическое программирование.

1.2 Сложностныс классы .

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

2.1 Проблема наименьших достаточных изменений

базы данных

2.2 Базы данных со статическими и динамическими ограничениями целостности ОЦ.

2.2.1 Ограничения целостности

2.2.2 Допустимые состояния и переходы .

2.2.3 Обновления БД
2.3 Консервативные обновления и проблема наименьших достаточных изменений ИДИ.
2.3.1 Совместность обновлений и ограничений целостности
2.3.2 Консервативные операторы обновлений.
2.4 Консервативные обновления для статических ОЦ .
2.4.1 Сложность проблем разрешения.
2.4.2 Алгоритмы для проблем НДИ и ПНДИ в статическом
случае.
2.5 Проблемы ИДИ и ПНДИ для полных БД
с динамическими ОЦ
2.5.1 Недетерминированные алгоритмы и сложность проблемы НДИ
2.5.2 Алгоритм для проблемы ПНДИ
2.6 Задачи поиска НДИ для частичных БД
2.7 Операторы расширения обновлений.
2.7.1 Обобщенные обновления и их расширения
2.7.2 Упрощение ограничений целостности
2.7.3 Прямой и обратный операторы расширения обновлений
2.8 Максималыюе расширение обновлений для
частичных БД.
2.9 Максимальные расширения для полных БД
3 Анализ поведения дедуктивных баз данных
3.1 Поведение дискретных интерактивных систем
3.2 Дедуктивные базы данных с обновлениями
3.2.1 Логические программы с обновлениями синтаксис . .
3.2.2 Логические программы с обновлениями семантика .
3.2.3 Классы ДБД и алгоритмические проблемы.
3.2.4 Примеры
3.3 Сложность проблемы перспективности
3.4 Сложность проблемы стабильности
3.4.1 стабильность .
3.4.2 Уфстабильность
3.4.3 ЗУстабильность
3.5 Сложность проблемы гомеостатичности
3.6 Сложность тотальной гомеостатичности
4 Анализ поведения мультиагентных систем
4Л Агенты и мультиагентные системы
4ЛЛ Архитектура и семантика МАсистем типа I .
4Л.2 Логики для описания свойств МАсистем.
4.2 Пример МАсистемы распределение ресурсов .
4.3 Поведение детерминированных МАсистем
4.3.1 Алгоритм проверки для детерминированных МАсистем
4.3.2 Сложность верификации
4.4 Поведение недетерминированных МАсистем
4.5 Вероятностные МАсистемы.
4.5.1 Неопределенность в МАсистем ах.
4.5.2 Синтаксис вероятностных МАсистем
4.5.3 Семантика вероятностных МАсистем.
4.5.4 Вычисление вероятностей переходов.
4.5.5 Верификация динамических свойств .
5 Семантика логических программ с интервальными вероятностями
5.1 Введение.
5.2 Интервальные вероятностные логические программы
5.2.1 Синтаксис.
5.2.2 Семантика возможных миров
5.2.3 Пробпема совместности
5.2.4 Семантика неподвижной точки и ее недостаточность
5.3 Семантика возможных миров описание и вычисление
5.3.1 Модели программ
5.32 Простые программы характеризация моделей . .
5.3.3 Простые программы явное вычисление моделей .
5.4 Когда неподвижной точки достаточно.
6 Семантика и сложность языка Рефал
6.1 Синтаксис и операционная семантика Рефала .
6.2 Денотативная семантика Рефалпрограмм
6.2.1 Рекурсивные программы и правила вычисления неподвижной точки.
6.2.2 Когда неподвижная точка вычисляется вызовами по значению
6.2.3 Вложение Рсфала в рекурсивные программы
6.2.4 О доказательстве свойств Рефалпрограмм .
6.3 Сложность одного шага Рсфалмашины
7 Сложностные спектры рекурсивных множеств и аппроксимируемость начальных отрезков полных проблем
7.1 Аппроксимация как метод решения сложных проблем
7.2 Основные обозначения и определения.
7.3 Сложностные спектры рекурсивных множеств.
7.4 Сводимость и аппроксимируемость
7.5 Нижние оценки аппроксимируемости трудных
проблем
7.6 Приложение к сложности схем и логических
систем.
7.7 Плотность полных проблем и сводимость к редким множествам
7.8 Нижние границы аппроксимируемости и ускорение вычислений
Литература


Понятия минимальной модели и ее вычисления через минимальную неподвижную точку сохраняются и для подкласса стратифицированных программ. Программа Р является стратифицированной в смысле [], если все ее предикаты Рр можно разбить на конечное число частей Рр = Ui~o Р* так> что Лля каждого г > 0 в тела предложений, определяющих предикаты из Р*. Р_? Рj при j < i. В частности, предикаты из Ро определяются предложениями без отрицаний. Ро, затем, имея часть модели для и;=0 Р^> МОЖНО ВЫЧИСЛИТЬ ее часть ДЛЯ Р*+1 и т. В общем случае, наибольшее внимание уделено исследованиям семантики, основанной на стабильных моделях [3|. Программа Лсс1исЬ(Р, I) не содержит отрицаний, т. У нее имеется минимальная модель /деЛдсЦР,/)- Интерпретация У называется стабильной моделью Р, если У — IясЛиы{р,1)- Не все нормальные программы обладают стабильными моделями. Проверка существования стабильной модели у базисной нормальной программы является МР-нолной задачей. Более подробные материалы об этих и других разновидностях логического программирования и их семантиках можно найти, например, в |2, , , 7, 7|. Работа || содержит обзор результатов о выразительной силе и сложности логического программирования, а в [8] приведен обзор основных известных фактов о дизъюнктивных логических программах. Мы предполагаем, что читателю известны основные понятия, связанные со сложностью вычислений и алгоритмов (см. Для полноты изложения напомним некоторые из них. Мы будем в этой работе рассматривать алгоритмические проблемы двух видов. У — это подмножество допустимых, распознаваемых, “хороших” данных из D. Нет”. Недетерминированный алгоритм для каждого входа порождает дерево вычислений. Он решает проблему, если для всякого входа из У в этом дереве есть путь вычисления, приводящий к ответу “Да” и ни для какого входа из D У такого пути нет (предполагается, что на любом пути алгоритм либо останавливается с ответом “Да”, либо вовсе не останавливается). В качестве основной формальной модели алгоритмов будут рассматриваться детерминированные и недетерминированные машины Тыоринга (ДМТ и НМТ). Для границы сложности f(n) (п — длина входа) через DTIME(f) (NTIME(f) обозначим класс проблем разрешения, решаемых ДТМ (ИТМ) за время, ограниченное функцией /(гг), а через SPACE(f) — класс проблем решаемых ДТМ с емкостной сложностью (в памяти), ограниченной функцией /(п). НТМ. Введем обозначения еще для нескольких сложностных классов, к которым будут относится изучаемые в работе алгоритмические проблемы. NTIME(2lin) = J%LxNTIME{2kn), SPACE(2lin) = U%LySPACE(2kn), EXPTIME = Uf=1DTIME(2n"), NEXPTIME = U? N EX РЕХ PTI ME = NTIME(P°"") = Uf=1/VM? НМТ. Еще одной моделью алгоритмов, полезной для определения сложности алгоритмических проблем, являются альтернирующие машины Тьюринга (ATM) (см. Как и НТМ альтернирующая МТ для каждого входа порождает дерево вычислений. Состояния ATM разбиты на два подмножества: V-состояния и 3-состояния. Такая машина допускает вход, если в дереве вычисления существует конечное поддерево допускающих вычислений такое, что для каждого V-состояния в него входят все сыновья, а для каждого 3-состояшія — один сын (V3-поддерево). Минимальная высота такого поддерева - это время вычисления ATM. Для детерминированного слож-ностного класса К через А К обозначим соответствующий еложностной класс для ATM. АР = PSPACE, APSPACE = EXPTIME, AEXPTIME = EXPSPACE и AEXPSPACE = EXPEXPTIME (см. Для сложностного класса К через со К обозначим класс дополнений проблем из К: со-К — {(D, DY) | (D, У) Є К}. Через Рк и NРк обозначим классы проблем разрешимых за полиномиальное время соответственно ДМТ и НМТ с оракулами из класса К. Между классами ДГР и PSPACE расположены классы полиномиальновременной иерархии PH: Eg = Пд = Р, Е^ = NР, П* =со-NP, Е? NP* = NPnp, Щ со-Ц,. Ef+1 = NPV, П? Sf+1. PH - и? Е?. Отметим, что перечисленные выше классы инвариантны относительно конкретной формализации алгоритмов, решающих проблемы (основное ограничение — отсутствие неограниченной распараллеливаемости). В случаях, когда сложность того или иного алгоритма будет оцениваться более точно (например, как “линейная”, “квадратичная” и т.