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

На правах рукописи

Дехтярь Михаил Иосифович

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

Специальность 05.13.17 — Теоретические основы информатики

2 2 ОНГ

Автореферат диссертации на соискание учёной степени доктора физико-математических наук.

Переславль-Залесский — 2009

003480288

Диссертация выполнена на кафедре информатики Тверского государственного университета.

Официальные оппоненты: член-корреспондент РАН,

доктор физико-математических наук, профессор А.Л.Семснов

доктор физико-математических наук, профессор И.А. Ломазова

доктор физико-математических наук, доцент В.Б. Новосельцев

ведущая организация: Институт прикладной математики

им. М.В.Келдыша РАН

Защита диссертации состоится 20 ноября 2009 г. в ч.О часов на заседании диссертационного совета ДМ002.084.01 при Учреждении Российской академии наук Институте программных систем РАН, расположенном по адресу: 152020, Ярославская область, Переславский район, с. Веськово, ул. Петра Первого, д. 4а.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института программных систем РАН

Автореферат разослан «_ /Й» октября 2009 г.

Ученый секретарь

диссертационного совета -Пономарева С.М.

Общая характеристика работы

Актуальность. Диссертация посвящена исследованию семантических проблем и анализу сложности алгоритмических проблем в таких областях теоретической информатики как дедуктивные базы данных, мудь-тиагентные системы, языки логического и функционального программирования. Многие из рассматриваемых в работе тем традиционно относят также к области искусственного интеллекта, поскольку рассматриваемые системы — активные базы данных, динамические дедуктивные базы данных и мультиагентные системы — демонстрируют черты разумного поведения. Все указанные области имеют не очень длинную историю (впрочем, как и вся теоретическая информатика), достаточно активно развиваются в последние десятилетия и являются вполне актуальными и в настоящее время. Это подтверждается, в частности, все возрастающим числом научных журналов и международных конференций, тематика которых включает перечисленные выше области.

Появление логического программирования обычно связывают с именами Дж. Робинсона, предложившего в 1965г. правило логического вывода, получившее название метода резолюций, Р. Ковальского, показавшего в начале 70-х, как на этом методе можно построить язык программирования, М. ван Эмдена, А. Колмероэ и Д. Уоррена, внесших в середине 70-х большой вклад в практическую реализацию языка Пролог. В те же годы методы автоматического вывода активно разрабатывались в ленинградский логической школе. Предложенный С.Ю.Масловым "обратный метод вывода" был, по-существу, эквивалентен методу резолюции.

Логические программы применяются в различных системах, основанных на знаниях. Они могут выступать в качестве языка запросов для реляционных баз данных, представлять интенсиональные компоненты дедуктивных баз данных, использоваться для вывода заключений в экспертных системах. В настоящей работе присутствуют четыре подхода к использованию логического программирования: во 2-ой главе логические программы задают ограничения целостности для транзакций и состояний в полных (реляционных) и частичных базах данных, в 3-ей главе логические программы с обновлениями определяют поведение динамических дискретных систем - осуществляют изменения их состояний, в 4-ой главе они выступают в качестве основных компонент интеллектуальных агентов, отвечающих за определение возможных действий агентов. Наконец, в 5-ой главе изучаются логические программы с ин-

тервальными вероятностями, которые используются для представления и вывода неточных знаний о фактах и событиях.

Вопросы интеллектуального выполнения внешних запросов на обновление в базах данных (БД) и базах знаний (БЗ), непрерывно поддерживающих ограничения целостности (ОЦ), исследовались с начала 80-х годов для класса пропозициональных БЗ. Первые шаги по формализации обновлений БЗ были предприняты П. Гарденфорсом (Gärdenfors Р.) и его коллегами, которые предложили некоторый набор постулатов, описывающих обновления БЗ при появлении новых знаний. Позже X. Катсуно (Н.Katsuno) и А. Мендельзон (A. Mendelzon) уточнили эти постулаты для пропозиционального случая. Их аксиомы неявно выражают важный принцип минимальных изменений, выполняемых в исходных моделях для получения результирующих. В каждом конкретном случае операторы обновления определяются с помощью некоторого явного критерия близости двух моделей. Такие критерии были предложены в работах Ю. Деяла (U.Dayal), К.Форбуса (Forbus К.) и других авторов. В большинстве работ расстояние между двумя моделями оценивалось через мощность их симметрической разности. В случае логики 1-го порядка ситуация с обновлениями БД и БЗ усложняется из-за возможности различных конструктивных интерпретаций отрицания. Целый ряд семантик отрицания был предложен в работах К. Апта (К. Apt), Н. Бидуа (N. Bidoit), ван Гельдера (van Gelder), Т. Пжимужинско-го (Т. Przymusinski), М.Гельфанда и В. Лифшица и др. Большинство авторов сосредотачивались на обновлениях БЗ. В этой области можно выделить работы X. Алфереса (J. Alferes) и Л.Перейры (L. Pereira), С. Чери (S. Ceri), Т. Пжимужинского и X. Тернера (H.Turner), Т. Ай-тера (Т. Eiter) и Г. Готлоба (G. Gottlob), Д. Лобо (J. Lobo) и др. В некоторых подходах при обновлениях изменяется не только БД, но и интенсиональная компонента БЗ. Кроме того, общей чертой предлагаемых методов обновления БЗ является то, что в качестве возможных результатов рассматриваются только специальные (минимальные, wf-, совершенные, стабильные и др.) модели. Это вполне оправдано для систем с интенсиональными знаниями. Однако этот подход не применим к БД, где ОЦ не должны изменяться и любая их модель является допустимой. Проблема наименьших допустимых обновлений для БД была рассмотрена Н. Спиратосом (N. Spyratos) с соавторами для очень простого подкласса ограничений целостности - правил вида I h. В главе 2 эта проблема исследована в гораздо более общих случаях.

В области динамических (дедуктивных) баз данных с обновлениями

(ДБД) внимание в первую очередь было уделено средствам задания обновлений, анализу их выразительных возможностей и сложности. Здесь можно отметить исследования С. Абитбуля (S. Abiteboul) и В. Виану (V.Vianu), А. Боннера (A.Bonner) и М. Кифера (М. Kifer), С. Манчанды (S. Manchanda) и Д. Уоррена (D. Warren) и др. При этом обновления, нарушающие ОЦ, как правило, считались недопустимыми. В главе 3 это ограничение снимается, изучаются свойства живучести ДБД, взаимодействующих со внешней средой, при этом каждая из взаимодействующих сторон могжет нарушать ОЦ.

Понятие интеллектуального агента сейчас является, пожалуй, основным в искусственном интеллекте (ИИ). Например, на нем построено все изложение в классическом учебнике по ИИ С.Рассела и П.Норвига. Исследования систем взаимодействующих интеллектуальных агентов занимают одно из ведущих мест в области ИИ и прикладного программирования. В первую очередь это объясняется тем, что мультиагентные системы (МА-системы) имеют широкую сферу применений, включающую такие разные области как управление бизнес-процессами, электронная торговля, Интернет-навигация, социальные и военные приложения и др. Такое разнообразие приложений привело к появлению многочисленных различных подходов к определению понятий агента и МА-системы (использующих, к тому же, разные уровни абстрагирования от конкретных систем). Среди авторов основных концепций и посвященных МА-системам монографий выделим М.Вулдриджа ( M.Wooldridge) и Н.Дженнингса (N. Jennings), A. Pao (A.Rao) и М. Джорджефа (M.Geor-geff), B.C. Субраманиана (V. S. Subrahmanian) с соавторами, И. Шохама (Y.Shoham) и К. Лейтон-Брауна (K.Leyton-Brown) Отметим также достаточно обширные обзоры на русском языке В.И. Городецкого и Д.А. Поспелова и монографию В.Б. Тарасова, в которых рассмотрены многочисленные предложенные модели, а также промышленные инструментальные средства, предназначенные для реализации МА-систем.

Рассматриваемая в диссертации проблема верификации МА-систем, относится к классу проблем, который под названием model checking (проверка на моделях программ) изучается уже ряд лет для абстрактных систем (диаграмм) переходов и конкретных программных систем. Содержательно, они формулируются так: по спецификации динамической системы (программы) определить, выполняется ли для нее некоторое свойство, выраженное в некотором формальном языке (как правило, языке какой-либо временной логики). Началом исследований в этой области послужили работы Е. Кларка (E.Clarke), Е. Эмерсона (E.Emerson)

и Дж. Сифакиса (J.Sifakis) в начале 80-х, которые были продолжены М. Варди (M.Vardi), П. Вольпером (P. Wolper), Д. Пеледом (D. Pcled), О. Купферман (O.Kupferman) и др. Результаты этого этапа были подытожены в классической монографии Е. Кларка с соавторами Современное состояние области отражено в монографии К. Байера (C.Baier) и Ж-П. Катоена (J-P. Katoen)2. В частности, в нее вошли результаты К.Куркубетиса (C.Courcoubetis) и М.Янакакиса (M.Yannakakis) по алгоритмам верификации вероятностных систем, которые мы используем при верификации вероятностных МА-систем в параграфе 4.4. Среди отечественных исследований по анализу поведения и верификации программ и динамических систем выделим работы Н.В. Евтушенко, В.А. Захарова, И.А. Ломазовой, В.Н. Непомнящего, А.К. Петренко, В.М. Смелянского, В.А. Соколова, Н.В. Шилова.

Отметим, что в разных областях ИИ постоянно возрастает интерес к исследованию систем, включающих стохастические элементы. Одна из таких областей — вероятностные базы знаний. Для задания их интенсиональной компоненты используются разные варианты вероятностного логического программирования. Они рассматривались в работах Д.Пула (D.Poole), и П.Хадцави (P.Haddawy), К. Барала (C.Baral), M. Гельфонда и Д.Раштона ( J.Rushton).Mx работы относятся к так называемому Баейсовскому подходу.

В ряде случаев бывает трудно точно оценить вероятность тех или иных фактов или событий. Тогда используют интервалы вероятностей, которые являются ограничениями для множества возможных истинных точечных вероятностных распределений. Несколько вариантов вероятностного логического программирования, основанное на Баейсовском подходе, определил и изучал Т.Лукашевич (T.Lukasiewicz) В его программах интервальное правило вида (H\B)[ci, сг] означает, что ciP(B) < Р(Н А В) < С2Р(В). Другой подход, основанный на вероятностной выполнимости (PSAT) берет свое начало в работе Буля по логике и теории вероятностей3 В ней он рассматривал конечное множество пропозициональных формул Fi,...,Fm над множеством атомов Ai,... Ап и предполагал, что вместо знаний об истинности или ложности формул известны их вероятности Prob(Fi) = pi, 1 < г < то. Буля интересовало можно ли так назначить вероятности Prob(Aj) — qj, 1 < j < п, пропозициональ-

1 Clarke Е.М., Grumberg О. and Peled D., Model checking, MIT Press, 2000. 314 p.

2Baier C., Katoen J-P. Principles of model checking. MIT Press, 2008. 975 p.

3G. Boole. An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities. Macmillan, London. 1854.

ным атомам, чтобы все утверждения о вероятностях формул Fi,...,Fm оказались верны. Этот подход естественным образом переносится на интервальные вероятности. Основанные на нем формализмы логических программ с интервальными вероятностями были предложены в работах Р.Энга (R.Ng) и В.С.Субраманиана (V.S.Subrahmanian), В. Лакшманана (V.Lakshmanan) и Ф.Садри (F. Sadri). Семантика интервальных вероятностных программ задается с помощью множества возможных миров, в которых для каждого события известно, произошло оно или нет. Вероятность события есть сумма вероятностей всех миров, в которых событие произошло. В работах Р.Энга и В.С.Субраманиана для рассматриваемого класса программ была также предложена семантика, основанная на вычислении минимальной неподвижной точки рекурсивного определения, задаваемого программой, и содержалось утверждение о совпадении этих двух семантик. В главе 5 это утверждение уточняется и дается точное описание семантики вероятностных логических программ.

Вообще, семантика рекурсивных определений вызывает постоянный интерес, поскольку рекурсия является одним из самых мощных средств разработки программ как в традиционных императивных языках программирования, так и в языках логического и функционального программирования, где она является основным таким средством. Многие результаты о рекурсивных программе« собраны в отдельной главе из книги 3. Манны (Z.Manna)4. В ней различные вычислительные стратегии оцениваются по отношению к вычислению семантики наименьшей неподвижной точки. В частности, показано (с ссылкой на диссертацию Морриса), что правило самой левой-самой внутренней замены ("вызов по значению") не является правилом вычисления неподвижной точки для класса всех рекурсивных программ. В то же время это правило используется в операционной семантике некоторых языков программирования. В частности, с его помощью определена семантика языка Рефал. Этот язык функционального программирования был создан В.Ф. Тур-чиным в 1966 году и успешно развивается уже более 40 лет им самим и группами его учеников в Москве, Нью-Йорке и Переславле-Залесском. Поэтому естественно возникла задача выделения класса рекурсивных программ, для которых правило вызова по значению вычисляет наименьшую неподвижную точку, и выяснения отношения Рефал-прогамм к этому классу. Еще одна проблема, связанная с языком Рефал, — это сложность выполнения одного шага Рефал-машиной.

4Манна 3. Теория неподвижной точки программ.// Кибернетический сборник. М.,вьщ. 15,1978. С.38-100.

Как мы уже отмечали, алгоритмические и сложностные проблемы, наряду с семантическими, занимают центральное место в нашей работе. Классическая теория алгоритмов занималась, в основном, классификацией алгоритмических проблем на разрешимые и неразрешимые, уделяя основное внимание последним. С появлением и развитием вычислительной техники алгоритмы заняли одно из важнейших мест как в практике вычислений, так и в в науке о них — информатике (computer science). В выдержавшей уже три издания книге Д. Харела (D. Harel)5 утверждается: "Алгоритмика — это больше, чем ветвь информатики. Она является ядром информатики и, со всей определенностью можно сказать, имеет важное значение для большинства наук, бизнеса и технологии." Появившаяся в 60-х годах XX века теория сложности алгоритмов и вычислений — сосредоточилась на классификации и изучении сложности разрешимых проблем. Ее "окончательная" цель состоит в определении сложности любой корректно сформулированной задачи. Другие цели связаны с установлением и пониманием отношений между различными вычислительными феноменами. Наибольших успехов теория добилась как раз в достижении этих целей. Многие результаты по сложности вычислений приведены в известном учебнике К.Пападимитриоу (C.Papadimitriou и вошли в недавние монографии Л.Хемаспандры (L.Hemaspaandra) и М. Огихары (M.Ogihara)- 2002г., Д.Козена (D.Kozen) - 2006г., О. Голдрей-ча (O.Goldreich) - 2008г.

Прежде всего нужно отметить выделение классов Р и NP задач, разрешимых за полиномиальное время детерминированными и недетерминированными алгоритмами, соответственно. Класс Р считается формализацией содержательного понятия "практически разрешимой задачи". Хотя вопрос о совпадении или различии этих классов "Р = NPT остается нерешенным, обнаружение в последние 38 лет многочисленных AfP-полных проблем (в том числе и в данной работе) позволило связать между собой задачи в совершенно различных областях информатики и математики. Кроме того, для многих конкретных алгоритмических проблем разными авторами была установлена полнота в ббльших слож-ностных классах PSPACE, EXPTIME и др.

Еще одно направление в теории сложности — сложность алгоритмов или "информационная" сложность — получило начало в работах

6Harel D. Algorithmics: the spirit of computing. 3rd ed. Pearson Education Ltd., 2004. 536p.

6 Формально этот вопрос был поставлен С. Куком в 1971г., но его содержательная постановка в терминах сложности доказательств была сделана К.Геделем в письме фон Нейману в 1956г.

А.Н.Колмогорова, А.А.Маркова и их учеников7. Здесь изучаются размеры (длины) программ, решающих соответствующую алгоритмическую проблему, при отсутствии или наличии некоторых ограничений на сложность (время, память) вычислений. Сложностью М^{АХ) аппроксимации начального отрезка длины х проблемы А мы называем длину самой короткой программы, вычисляющей А(у) при у < х за время < f(y). Представленные в работе результаты о сложности аппроксимации были получены автором в конце 70-х - начале 80-х годов. За рубежом исследования связи между колмогоровской и вычислительной сложностью продолжались в работах Р. Бука (R.Book), Ю. Харт-маниса (J.Hartmanis), Д. Лутца (J.Lutz) м др. В частности, недавно были обнаружены неожиданные связи между ограниченной колмогоровской сложностью и и размерностью Хаусдорфа в геометрии фракталов. Среди отечественных авторов имеющих серьезные достижения в теории сложности алгоритмов и вычислений отметим: А.П. Бельтюкова, Н. К. Верещагина, Д.Ю. Григорьева, Ю.В. Матиясевича, A.A. Разборо-ва, А.Л. Семенова, А.О. Слисенко.

Цели работы. Цели работы состояли в разработке теоретических основ создания программных систем для новых информационных технологий, исследовании информационных структур и в анализе основанных на знаниях динамических моделей взаимодействующих информационных процессов и алгоритмов верификации их поведения.

Для достижения этих целей в работе исследовались следующие проблемы.

1) Проблема корректного выполнения обновлений полных (реляционных) и "частичных" баз данных с сохранением статических и динамических ограничений целостности.

2) Разработка моделей дискретных динамических систем, основанных на логических программах с обновлениями, и анализ устойчивого поведения таких систем во взаимодействии с внешней средой.

3) Разработка моделей детерминированных, недетерминированных и вероятностных мультиагентных систем и верификация динамических свойств поведения таких систем.

4) Исследование семантик языка дизъюнктивных логических программ с интервальными вероятностями и алгоритмов их вычисления.

5) Семантика и верификация программ языка функционального про-

73а рубежом независимо тот же подход был предложен Р.Соломоновым (R.Solomonoff) и Г.Чейтиным (G.Chaitin).

граммирования Рефал и анализ сложности его вычислений. 6) Построение теории аппроксимации алгоритмических проблем на начальных отрезках и исследование сложности аппроксимации трудных проблем в различных сложностных классах.

Методы исследования. В диссертации используются методы таких разделов теоретической информатики как теория баз данных, логическое программирование, теория сложности алгоритмов и вычислений, искусственный интеллект, а также математических дисциплин: математической логики и теории алгоритмов.

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

1. Установлены оценки сложности задач, связанных с проблемой наименьших достаточных изменений (НДИ) при выполнения обновлений БД и предложены эвристические алгоритмы для решения проблемы НДИ для статических и динамических ограничений целостности и алгоритмы для максимального расширения обновлений и упрощения ограничений целостности.

2. Определена формальная модель взаимодействия интеллектуального агента - динамической дедуктивной базы данных - с внешней средой и установлена сложность верификации свойств устойчивого поведения (перспективности, стабильности и гомеостатичности) для различных классов таких систем, определяемых типом логической программы с обновлениями в качестве интеллектуальной компоненты системы и типом условия, выделяющего допустимые состояния.

3. Определены формальные модели детерминированных, недетерминированных и вероятностных мультиагентных (МА-) систем, базирующиеся на архитектуре IMPACT, и получены оценки сложности верификации свойств поведения МА-систем, выразимых средствами временных логик, для различных классов МА-систем, различающихся типами используемых в качестве интеллектуальной компоненты агентов логических программ, количеством агентов в системе, количеством различных видов сообщений и количеством параметров в описаниях состояний.

4. Ранее определенный класс логических (р-) программ с интервальными вероятностями расширен до класса дизъюнктивных логических {йр-) программ. Для обоих классов изучено соотношение между теоретико-модельной семантикой "возможных миров" и семантикой минимальной неподвижной точки. Доказана №-полнота проблемы совместности (существования модели) и и проблемы следования для р- и ¿^-программ. Получено явное описание множества моделей, задаваемых р- и ф-программами Построены алгоритмы для вычисления теоретико-модельной семантики р- и ¿р-программ, использующие специальные эвристики для сокращения перебора.

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

6. Исследована сложность аппроксимации трудных проблем более простыми на начальных отрезках входных данных. В частности, получены оценки сложности аппроксимации проблем, которые полны или трудны для различных детерминированных и недетерминированных сложностных классов и установлена связь между верхними и нижними оценками сложности вычисления проблемы и сложностью ее аппроксимации.

Теоретическая и практическая значимость. Работа носит теоретический характер. Результаты о сложности задачи отождествления для языка Рефал могут быть использованы (и использовались автором) при разработке компиляторов этого языка. Алгоритмы выполнения "интеллектуальных" обновлений могут быть использованы при разработке новых СУБД. Результаты о высокой сложности задач анализа поведения динамических баз данных и мультиагентных систем с одной стороны указывают на тупики, с которыми могут столкнуться разработчики систем верификации, а с другой — подталкивают к созданию интерактивных программных средств для моделирования и анализа свойств таких систем (набросок требований к программной системе такого типа приведен в [18]). Проведенное исследование семантики языка вероятностных программ, введенного Энгом и Субраманианом, показало, что в каче-

стве языка представления интенсиональных знаний в вероятностной БД он чересчур сложен и нуждается в существенных упрощениях.

Материалы диссертации могут использоваться (и уже неоднократно использовались автором) при чтении специальных курсов студентам и аспирантам, обучающимся математическим основаниям информатики. Они также послужили основой при выполнении ряда выпускных и дипломных работ и магистерских диссертаций на кафедре информатики Тверского госуниверситета.

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

Всесоюзные конференция по математической логике ( Кишенев, 1976; Новосибирск, 1979; Новосибирск, 1984), 8-th Symp. on Mathematical Foundation of Computer Science ( Praga, 1979), Всесоюзная научная конф. "Проблемы совершенствования, тестирования, верификации и отладки программ" (Рига, 1986), 10th International Symp. on Logic Programming (USA, Ithaca, 1994), 12th International Conf. on Logic Programming (Japan, 1995), 2nd and 3-rd Int. A.P.Ershov Memorial Conference "Perspective of Systems Informatics"(Новосибирск, 1996 и 1999), 4th International Symposium Logical Foundation of Computer Science'97, (Ярославль, 1997), 14th International Conference on Logic Programming (London, 1997), 4th International Conference Logic Programming and Nonmonotonic Reasoning'97 (Dagstuhl Castle, Germany, 1997), Joint International Conf. and Symp. on Logic Programming (Manchester, 1998), Seventh International Colloquium on Numerical Analysis and Computer Science with Applications (Plovdiv, Bulgaria, 1998), 13th International Conference on Logic Programming, (New Mexico, USA, 1999), 5th International Conference, Logic Programming and Nonmonotonic Reasoning'99 (El Passo, USA, 1999), First International Symp. on Foundations of Information and Knowledge Systems (FoIKS 2000) (Burg, Germany, 2000), First Int. Conf. on Computational Logic, CL-2000 (London, 2000), Конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова ( Новосибирск, 2001), International Workshop "Logic and Complexity in Computer Science" ( Creteil, France, 2001), 8th European Conference on Logics in Artificial Intelligence (Cosenza, Italy, 2002), IEEE International Conf. on Artificial Intelligence Systems. (Дивно-морское, 2002 и 2003), Second St.Petersburg Days of Logic and Computa'bi-lity, (St.Petersburg,Russia, 2003), Первая Всероссийская научная конференция "Методы и средства обработки информации", (Москва, МГУ,

2003), 1-ой, III-ий, IV-ый, V-ый Межд. научно-практический семинар (конференция) "Интегрированные модели и мягкие вычисления в искусственном интеллекте "(Коломна, 2003, 2005, 2007, 2009), IX-ая, Х-ая и XI национальная конференции по искусственному интеллекту с международным участием (Тверь, 2004; Обнинск, 2006; Дубна, 2008), 20th International Conference on Logic Programming (San Malo, France, 2004), 8th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'05)(Cosenza, Italy, 2005).

Результаты диссертации также докладывались автором на семинарах в Новосибирском госуниверситете (1976-1981), Институте математики СОАН (1976-1981), Вычислительном центре СО АН (1978-1981), Тверском госуниверситете (1982-2008), University Parisl2-Val de Marne (Paris,1996), Tel-Aviv University (1998, 2004), University of Maryland (College Park, 1998), University of Nantes (1999,2000, 2001, 2002, 2003), University of Kentucky (Lexington, 2002).

В разные годы работа поддерживалась грантом INTAS (Grant 942412) и грантами РФФИ 95-01-01321, 96-01-00395, 97-01-00973, 98-0100204, 99-01-00374, 01-01-00278, 02-01-00652, 04-01-00015,04-01-00565, 0501-01006, 07-01-00637, 08-1-00241.

Публикации. Список публикаций по теме диссертации приведён в конце автореферата и включает 47 печатных работ, 7 из которых опубликованы в изданиях, входящих в список ВАК (они выделены полужирным шрифтом), и еще 2 работы [48,49] приняты в печать в таких изданиях. 12 работ опубликованы в томах серии Lecture Notes in Computer Science (Artificial Intelligence) издательства Springer.

Структура и объем диссертации. Диссертация состоит из введения, семи глав основной части и списка литературы. Общий объем работы — 383 стр. Список литературы содержит 190 наименований.

Краткое содержание работы

Глава 1 носит вспомогательный характер. В ней собраны основные обозначения и определения, связанные со сложностными классами и логическими программами, которые широко используются в остальной части работы.

В главе 2 рассматривается проблема, которая связана с возможностями БД нового поколения интеллектуально выполнять внешние запросы

на обновление. Системы управления такими базами данных можно рассматривать как интеллектуальные агенты, цель которых — выполнять получаемые из внешней среды приказы на обновление и при этом поддерживать корректность состояний базы данных и их транзакций (переходов из одного состояния в другое). Знания о корректности представляются некоторыми логическими средствами, задающими ограничения целостности - условия, которым должны удовлетворять состояния и переходы.

Основное содержание этой главы основано на работе автора [35], которая, в свою очередь, продолжает и расширяет результаты по этой проблеме, полученные вместе с соавторами в работах [22, 23, 24, 26, 28, 29, 30]. В этих работах указанная проблема изучалась для статических ограничений целостности, фильтрующих допустимые состояния БД. Некоторые результаты для них представлены в параграфе 2.4 Основное же внимание в этой главе уделяется более широкому классу -динамическим ограничениям целостности (ДОЦ), которые выделяют допустимые транзакции, т.е. переходы из одного состояния БД в другое. Примерами динамических ограничений целостности являются, например, условия: "зарплата не должна уменьшаться", "на должность ведущего научного сотрудника можно назначать лишь того, кто работает в должности старшего научного сотрудника", "принимать заказ на продажу N принтеров следует лишь тогда, когда их текущее количество на складе не меньше N + 2" и т.п.

Более точно рассматриваемая задача формулируется следующим образом: по заданной логической программе Ф, формализующей динамические ограничения целостности (ДОЦ), исходному состоянию БД I и запросу на обновление Д, включающему множество Д+ добавляемых к I фактов, множество Д~ фактов, которые нужно удалить из I, и множество А* пар фактов, в которых первый должен быть заменен на второй, требуется найти такое минимальное изменение I' состояния I, что при переходе от I к I' выполнено обновление А и не нарушено ни одно из ограничений Ф (т.е. гарантируется, что Д+ С I', I' П Д~ = 0, для всякой пары (а,Ь) € А*, если а е I, то а<£Г иЪ&Г,и <1,Г> |=Ф/

Как мы уже отмечали, мы называем эту проблему проблемой наименьших достаточных изменений (проблемой ИДИ). Поскольку результирующих состояний, удовлетворяющих указанным условиям, может быть несколько, мы также рассматриваем проблему перечисления всех таких состояний — проблему ПНДИ.

В качестве критерия близости состояний БД чаще всего в работах по обновлениям баз данных и знаний использовался критерий, основанный на симметрической разности состояний. В [22] мы предложили соединить этот критерий с критерием максимального пересечения. Согласно этому комбинированному критерию вначале минимизируется множество удаляемых из БД известных данных, а затем минимизируется добавление новых данных. Представляется, что это лучше соответствует идеологии баз данных.

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

В параграфе 2.2 приводятся определения основных понятий: логического языка и задаваемых в его терминах статических (ОЦ) и динамических (ДОЦ) ограничений целостности. Они представляются с помощью обобщенных логических программ. Определены понятия частичного и полного состояний БД, выполнения ДОЦ на переходе из одного состояния в другое. Обновления задаются множествами команд вида ДОБА-ВИТЬ(факт), УДАЛИТЬ(факт) и ЗАМЕНИТЬ(фактп1, факгп2). Они выполнены на переходе, если факты из команд ДОБАВИТЬ присутствуют в результирующем состоянии, факты из команд УДАЛИТЬ в нем отсутствуют и каждый факт1 из команд ЗАМЕНИТЬ, присутствующий в исходном состоянии, заменен на соответствующий фа,ктп2 - в заключительном.

В параграфе 2.3 определена совместность ДОЦ Ф с обновлением Д, которая означает, что множество переходов Тг(Ф,Д), удовлетворяющих Ф, на которых выполнено Д, содержит хотя бы один переход. Совместность же Ф с Д для состояния БД / означает, что имеется хотя бы одно состояние I' такое, что переход </,/'>€ Тг(Ф, Д), т.е. можно так выполнить запрос на обновление Д, что ДОЦ Ф будут выполнены на соответствующем переходе. Показано, что обе проблемы совместности

являются ^-полными (теорема 2.1).На множестве переходов определяется сильный оператор непосредственной выводимости Т§(< I, Г >), котрый является монотонным и имеет эффективно вычислимую неподвижную точку. Во 2-ом пункте определяется понятие консервативны-ого оператора обновления который для каждого состояния БД I такого, что Д совместно с Ф для I, выдает ближайшее к I состояние Фф,д(-0 = Л такое что переход <1, /'>€ Тг(Ф, Д).

В параграфе 2.4 приводятся некоторые результаты для случая статических ОЦ. В частности, исследована сложность некоторых алгоритмических проблем разрешения, связанных с проблемой НДИ. Даже в простейших случаях они оказываются достаточно сложными. Так, например, если статические ОЦ заданы базисной дефинитной логической программой, то проблема включения литерала в результат-решение проблемы НДИ является со№-полной проблемой для частичных БД и Неполной проблемой для полных БД (теоремы 2.3 и 2.4). В этом же параграфе также рассматриваются и анализируются несколько алгоритмов для решения проблем НДИ и ПНДИ в статическом случае.

Результаты в параграфах 2.5 - 2.9 относятся к БД с динамическими ограничениями целостности. Параграф 2.5 посвящен проблемам НДИ и ПНДИ для полных БД. В его первом пункте приведен недетерминированный алгоритм для проблемы НДИ. В теореме 2.7 доказано, что эта проблема для реляционных БД является полной в классе сложности Р№//Ор1Р[С>(1о£п)] . Во втором пункте предложен алгоритм ПНДИ, решающий соответствующую проблему за время линейное от размеров всех параметров и экспоненциальное от количества потенциально добавляемых и удаляемых фактов.

В параграфе 2.6 для частичных БД построен алгоритм ЧНДИ, который решает проблему НДИ за полиномиальное время (теорема 2.9).Предложен также алгоритм для решения проблемы перечисления всех минимальных корректных результатов обновлений (проблемы ПНДИ) и получены оценки его сложности, которые экспоненциально зависят от числа фактов, не попавших в обновление, и полиномиально — от размера ДОЦ (теорема 2.10).

Из этих результатов следует, что каждый новый явно добавляемый или удаляемый факт существенно уменьшает пространство поиска возможных решений и, следовательно, время их поиска. Каждое упрощение ДОЦ — удаление ограничения или литерала из его условия — также упрощает поиск решения, так как уменьшает время на проверку выполнения ДОЦ. Поэтому в параграфах 2.7 - 2.9 для поиска практи-

ческого решения проблемы НДИ мы распространяем на динамические ограничения целостности метод предварительного корректного расширения исходного запроса на обновление и одновременной оптимизации ДОЦ, примененный в работах [26, 28, 30] для статических ОЦ. Такая оптимизация обновлений не зависит от исходного состояния БД и может быть проведена на этапе трансляции запроса на обновление. Идея метода состоит в том, что запрос на обновление Д можно последовательно и корректно расширить, итеративно "протаскивая" его через ДОЦ Ф. Корректность такого расширения означает, что оно сохраняет неизменным множество допустимых для Ф и Д переходов Тг(Ф,Л). Целью является получение после конечного числа итераций максимального корректного расширения Д' исходного запроса на обновление и наиболее простого представления Ф' ограничений целостности. Использование пары Ф', Д' вместо Ф, Д может существенно ускорить алгоритмы поиска НДИ. Результаты, представленные в параграфе 2.7 дают теоретическое обоснование предложенного подхода к оптимизации обновлений на этапе трансляции и имеют ясный практический смысл. В нем определены операторы, применение которых к исходным ДОЦ и обновлению доставляет оптимальную (по отношению к порядку на парах) пару вида обновление/ДОЦ. Эта пара состоит из максимально расширенного обновления и минимальных по размерам ДОЦ, эквивалентных исходной паре. В пункте 2.7.2 описаны два метода упрощения ДОЦ, а в пункте 2.7.3 для каждого из видов БД определен прямой и обратный операторы расширения обновлений. В параграфе 2.8 предложен алгоритм, который строит такую оптимальную пару для класса частичных БД за полиномиальное время (теоремы 2.12, 2.13). Существование аналогичного алгоритма для полных БД маловероятно, поскольку предложение 2.15 (2)показывает, что в таком случае выполнялось бы равенство Р=№. Поэтому в общем случае в параграфе 2.8 предлагается использовать для полных БД итерацию прямого и обратного операторов расширения обновлений, которая дает некоторую аппроксимацию оптимальной пары (обновление/ДОЦ). Более того, для одного практически интересного класса полных БД, а именно для полных БД, имеющих ДОЦ с позитивными телами правил, оптимальные пары вида (наибольшее корректное обновление/ наиболее простые эквивалентные ДОЦ) все же можно находить за полиномиальное время (теорема 2.17).

Глава 3 посвящена анализу поведение пары взаимодействующих агентов динамическая дедуктивная база данных - внешняя среда на протяжении произвольного конечного или даже потенциально бесконечного

числа шагов. В параграфе 3.1 определяются некоторые достаточно общие рамки для классификации и анализа многих естественных свойств устойчивого поведения дискретных интерактивных систем. Дискретная природа такой системы Э проявляет себя, по меньшей мере, в двух отношениях. Во-первых, й ведет себя пошагово, что позволяет фиксировать ее состояния до и после каждого шага. Во-вторых, состояния Б могут, как правило, быть описаны с помощью конечного числа отношений на значениях параметров системы. Мы будем предполагать, что фиксировано некоторое пространство £ состояний Б и что действия Б (т.е. переходы системы из одного состояния в другое) представляются с помощью некоторого бинарного отношения (-5 на Е. Состояния системы делятся на допустимые и недопустимые, в которых система не может функционировать должным образом. Это подразделение определяется некоторым свойством состояний Ф, которое играет роль ограничения целостности (ОЦ). (ОЦ, рассматриваемые в этой главе, в предыдущей назывались статическими . ) Тот факт, что состояние £ допустимо, т.е. удовлетворяет ОЦ Ф, будем обозначать как £ |= Ф. Интерактивная природа поведения систем, которые мы рассматриваем, подразумевает существование активной внешней среды системы и возможности влияния этой среды на состояния системы в процессе ее эволюции. Действия внешней среды на состояния системы представляется с помощью отдельного бинарного отношения ——> на множестве которое мы будем называть возмущением. В нашем подходе фундаментальное различие между системой и внешней средой определяется уровнем наших знаний о них. Предполагается, что теория, задающая поведение системы, является полностью известной. Что касается внешней среды, то она является недетерминированной — для нее можно лишь оценить "сверху" множество возможных возмущений и известно, как определить результат применения конкретного возмущения к состоянию системы. Но невозможно для данного состояния точно предсказать, какое именно из возможных возмущений будет к нему применено. Например, если рассматривать банк как интерактивную дискретную динамическую систему, то можно видеть, что имеется некоторый полный список услуг, предоставляемых банком клиентам, при выполнения каждой из которых некоторая транзакция (действие) изменяет состояние банка. Но невозможно точно предсказать, какие именно заказы на услуги (возмущения) появятся в тот или иной момент.

В этих терминах эволюция дискретной системы может быть пред-

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

(1) и = £0 ^ £{ К 5 ¿1 Н 5 £2 -

Такие траектории имеют тип возмущение-действие и называются с1а-траекториями.

(2) и = £0 н 5 £х К 5 £1 ¿2 ...

Эти траектории имеют тип действие-возмущение и называются ас1-траекториями.

Рассматриваются три вида свойств живучести системы. В первой ситуации конечная ас!-траектория начинается в недопустимом состоянии и система совместно с внешней средой могут в конце концов могут достигнуть допустимое состояние. Исходное состояние £о в этом случае называется перспективным. Во второй ситуации ас1-траектория стартует в допустимом состоянии £о и первое действие выполняет система. Ее действия могут приводить к недопустимым состояниям, которые возмущениями внешней среды переводятся в допустимые, т.е. {= Ф для всех г > 0. Такие траектории называются стабильными. В третьей ситуации с!а-траектория стартует в допустимом состоянии £о , к которому применяется возмущение внешней среды. Если при этом допустимость нарушается, то система должна восстановить ее в результате своего действия, т.е. и здесь £{ (= Ф для всех i > 0. Такие траектории называются гомеостатичными.

С технической точки зрения свойство перспективности близко связано с хорошо известной в искусственом интеллекте проблемой планирования, которую можно сформулировать, как проблему существования плана (траектории), приводящего систему в заданное состояние или в состояние, удовлетворяющее некоторым заранее заданным условиям. Содержательный смысл других определений следующий. Вдоль гомеостатичной траектории система способна регулярно восстанавливать свойство Ф в ответ на разрушающие его возмущения внешней среды Дуально, вдоль стабильной траектории действия среды компенсируют возможные разрушающие Ф действия системы.

Траектории каждого из указанных типов (ас!- или с!а-), начинающиеся в фиксированном состоянии £о, образуют деревья траекторий с корнем £о : Тг1а(£й) и То<г(£о)> соответственно. В терминах этих де-

ревьев можно формализовать многие естественные свойства живучести интерактивных динамических систем. Пусть Qi, Qi € { V, 3}. Пусть S -система, действия которой представляются отношением bg , функционирующая в среде, возмущения которой представляются отношением , и пусть £q - это некоторое состояние системы. Скажем, что система S является QiQ2-20Meocrnamu4HoU в состоянии £о, если в дереве траекторий Tria(£o) имеется (Зхфг-поддерево с тем же корнем, в котором все ветви являются бесконечными гомеостатичными траекториями. Система является Q1Q2-стабильной в £о, если в дереве траекторий X!j(i(£o) имеется ¿^(Эг-поддсрево с тем же корнем, в котором все ветви являются бесконечными стабильными траекториями.

В параграфе 3.2 определяются дедуктивные базы данных с обновлениями (ДБД), основой для формализации которых выступают логические программы с обновлениями. Эти программы представляют из себя конечные множества предложений вида Head <— Body, где голова правила Head — это интенсиональный атом (запрос) а тело Body — это последовательность литералов, элементарных обновлений баз данных вида insert(Fact) или delete(Fact) (Fact — это экстенсиональный атом), присваиваний вида X е (X — переменная, е — арифметическое выражение) и арифметических ограничений вида е\ < е^- На эти программы накладываются условия стратифицированности, обеспечивающие конечную завершаемость выполнения вызова каждой цели. Операционная семантика логических программ с обновлениями состоит в недетерминированном выборе предложения для разрешения очередной цели (как в обычном логическом программировании) и в последовательном слева-направо разрешении подцелей в теле выбранного предложения ( как в Прологе). Вызов каждой цели *— а программы V зада-

а

ет отношение перехода hp на состояниях системы. Дедуктивная база данных с обновлениями (ДБД) — это система ¡3 =< V U { <— ai,..., <— ап }, Ф >, которая включает логическую программу с обновлениями V, фиксированное множество целей { <— а\,..., <—' а„}, реализующих действия ДБД, и ОЦ Ф , которые задают конструктивное представление некоторого свойства состояний БД. ДБД В задает на

ai

множестве состояний БД отношение переходов 1~в= U™=1 У-р , являющееся объединением отношений для отдельных целей.

Мы классифицируем логические программы, налагая ограничения на вид их предложений. Логическая программа является V позитивной, если в ней нет отрицаний, она расширяющая, если обновление

delete не используется в ее предложениях. V называется базисной, если все ее предложения базисные. Она является плоской, если все термы в литералах ее предложений являются либо переменными, либо константами. V называется ветвящейся, если она не рекурсивна. V называется продукционной, если она определяет один интенсиональный предикат q/О и все ее предложения являются продукциями, т.е. имеют вид Соп\ Л ... Л Сопт ==> Act\,..., Actn, где каждое "условие" Сощ — это экстенсиональный литерал, а каждое "действие" Actj является элементарным обновлением.

Рассматриваемые ограничения целостности принадлежат одному из следующих трех классов.

/Со : Ф сохраняется при расширениях состояний и все минимальные расширения состояния, удовлетворяющие Ф. можно эффективно перечислить.

ICi : проблема £ \= Ф принадлежит классу Р (т.е. разрешима за полиномиальное время).

/С*2 : проблема £ \= Ф принадлежит классу PSPACE (т.е. разрешима с полиномиальной памятью).

В частности, класс /Со содержит ОЦ, задаваемые базисными ДНФ, логическими программами без отрицаний, а также некоторые монотонные свойства графов (например, связность). Хорошо известные функциональные зависимости и многие свойства размеров состояний БД (например, четность) принадлежат классу 1С\. Класс ICi содержит ОЦ, выражаемые формулами логики 1-го порядка и др.

Возмущения внешней среды задаются парой 5 = (Д+,Д~) конечных множеств атомов. £ £' означает, что D+ = £' \ £ С Д+ и D~ = £ \ £' С Д~. Таким образом, ¿-возмущение задает весьма простые теоретико множественные границы для возможных множеств изменений состояний БД, которые не зависят от самих состояний.

В параграфе 3.3 анализируется сложность проблемы перспективности. Теорема 3.1 содержит оценки сложности этой проблемы для различных подклассов ДБД. Они варьируются от линейной сложности для расширяющих позитивных продукционных ДБД с ОЦ из /Со, до полноты в классе EXPSPACE — для плоских продукционных ДБД с ОЦ из 1Сч и для плоских стратифицированых ДБД. Если в продукциях допустить сложные термы, то проблема становится неразрешимой.

Параграф 3.4 посвящен анализу различных вариантов проблемы стабильности. Для 33-стабильности (теорема 3.2) и W-стабильности они

аналогичны оценкам сложности для перспективности. Сложность проблем УЗ-стабильности и ЗУ-стабильности несколько выше (теоремы 3.3 и 3.4). В частности, для плоских стратифицированых ДБД эти проблемы являются ЕХРЕХРТ1МЕ-полными. Но и эти проблемы разрешимы за полиномиальное время для расширяющих позитивных продукционных ДБД с ОЦ из /С0.

Сложность проблемы УЗ- гомеостатичности для различных классов ДБД рассматривается в параграфе 3.5.Свойство УЗ-гомеостатичности представляется одним из самых интересных с практической точки зрения. Его выполнение для системы и некоторого ее (текущего) состояния означает, что какими бы ни были возмущения внешней среды, у системы будет достаточно средств, чтобы их компенсировать и на каждом шаге возвращаться в допустимое состояние. Теорема 3.5 устанавливает сложность УЗ-гомеостатичности для различных классов ДБД. Она показывает, что для монотонных ОЦ эта проблема разрешима за полиномиальное время, но при допущении их немонотонности сложность возрастает - проблема становится ЕХРТ1М/^-трудной. Однако, если каждый факт, удаляемый внешней средой, может быть ею возвращен в базу данных, то УЗ-гомеостатичность можно распознать в детерминированной полиномиальной памяти (теорема 3.6).

Параграф 3.6 посвящен исследованию проблемы тотальной гомеостатичности, т.е. проверке гомеостатичности системы на всех допустимых состояниях. Рассматривается самый интересный вариант гомеостатичности — УЗ-гомеостатичность. Приводимые далее результаты показывают, что проверка УЗ-гомеостатичности на всех состояниях оказывается существенно более простой, чем на отдельном состоянии. Теорема 3.7 утверждает, что в классе продукционных ДБД, не использующих отрицаний в программах, и с ОЦ из класса /Со проблема тотальной УЗ-гомеостатичности эффективно разрешима. Заметим, что обновления БД, при работе таких систем не обязательно монотонны, так как действия их продукций могут включать удаления фактов. Теорема 3.8 оценивает сложность тотальной УЗ-гомеостатичности для более широкого класса ветвящихся программ без отрицаний. Эта проблема разрешима за полиномиальное время при условии, что размер интенсиональной сигнатуры системы ограничен некоторой константой. Без этого ограничения она является со-А^Р-полной. Технически самый сложный результат в этом параграфе теорема 3.10 относится к самому большому из рассматриваемых классов ДБД - классу БАТАЬОС" всех плоских стратифицированных программ. В ней доказано, что тотальная

\/3-гомеостатичность для этого класса является NEXPEXPTIME-полной проблемой.

Глава 4 посвящена анализу поведения мультиагентных систем (МА-систем), в которых все агенты имеют одинаковую архитектуру, т.е. "равноправны" по возможностям получения и передачи информации. Для таких систем изучются не только специальные свойства устойчивого поведения (как в предыдущей главе), но и произвольные свойства, выразимые средствами временных логик. В параграфе 4.1 перечисляются основные свойства интеллектуальных агентов и мультиагентных систем, сформулированные разными авторами. Приведены особенности архитектуры IMPACT, разработанной интернациональной группой в университете Мериленда,8 на которой основана рссматриваемая нами модель МА-систем, и приводится точное описание этой модели. Кратко определены временные логики, используемые для оисания свойств поведения МА-систем. Перечислены основные параметры, по которым классифицируются МА-системы. К ним относится детерминированный или недетерминированный способ выбора действий агентами системы, отсутствие или наличие переменных и отрицаний в логических программах, управляющих выбором допустимых действий, допустимость удалений из баз фактов, размерность предикатов, количество разных видов сообщений в системе, число агентов в системе. В параграфе 4.2 приводится небольшой пример, иллюстрирующий возможности рассматриваемых нами МА-систем. Это один из вариантов известного в литературе примера распределения ресурсов типа "Белоснежка и семь гномов". Параграф 4.3 посвящен анализу поведения детерминированных МА-систем. Его первый пункт содержит описание алгоритма верификации детерминированных МА-систем, который служит основой для получения верхних оценок сложности. Во втором — представлены оценки сложности проблемы MA-BEHAVIOR для ряда классов детерминированных МА-систем (теорема 4.1) Они приведены в следующей таблице 1. Ее первые три столбца определяют классы рассматриваемых МА-систем. Столбцы "Баз."и "Расш."позволяют различить базисные и небазисные системы, а также расширяющие (без удалений) системы и системы с удалениями. В столбце "Параметры"указаны некоторые ограничения на параметры архитектуры МА-систем, приводящие к меньшей сложности верификации. В частности, N обозначает размер всего описания системы, m - число ее агентов, к - это максимальная раз-

8Subrahmanian V. S., Bonatti P., Dix J., et al., Heterogeneous agent Systems, MIT Press, 2000.514p.

23

Баз. Расш. Параметры Логика Сложность

Да Да позитивные LTL Р

т**г = 0(к^Лг) LTL Р

фикс. т> 2 LTL PSPACE

фикс, г > 1 LTL PSPACE

Нет FLTL PSPACE

Нет Да позит., фикс, к LTL Р

позитивные LTL EXPTIME

Нет фикс, к FLTL PSPACE

FLTL EXPSPACE

мерность атомов действий и сообщений (в пропозициональном случае к = 0), г - это число различных сигналов (т.е. сообщений). В столбце "Логика"указан логический язык, в котором формулируются свойства поведения соответствующего класса МА-систем.

В параграфе 4.4 анализируется поведение недетерминированных МА-систем (теорема 4.2). Сложность верификации для них, естественно, оказывется выше и варьируется от NP-полноты до двойной экспоненты.

В параграфе 4.5 рассмотрено поведение вероятностных МА-систем. Источников неопределенности два: почтовая подсистема, которая может задерживать и даже терять сообщения, и неоднозначность результатов выполнения действий. В пунктах 2 и 3 определены синтаксис и семантика рассматриваемых систем и показано, как вероятностной МА-системе сопоставляется соответствующая цепь Маркова. В пункте 4 приведен полиномиальный алгоритм вычисления вероятностей перехода этой Марковской цепи. Это дало возможность в пункте 5 использовать известные результаты о сложности верификации Марковских цепей для порлучения оценок сложности проблемы MA-BEHAVIOR для вероятностных МА-систем (теоремы 4.4, 4.5). В частности, существует алгоритм, который проверяет выполнимость FLTL-формулы F на состоянии S базисной вероятностной MAC А в памяти, полиномиальной от |А| и |F|. А вероятность pa(Sq, F) формулы F в состоянии So для такой же системы можно вычислить за время, экспоненциально зависящее от |А| и 1^1.

Глава 5 посвящена логическим программам с интервальными вероятностями. Формализмы логических программ с интервальными вероятностями, рассматриваемые в ней, были предложены в работах Р.Энга

и В.С.Субраманиана 9. В параграфе 5.2 мы расширяем их, допуская дизъюнкции в головах правил. Дизъюнктивные логические программы с интервальными вероятностями (ёр-программы) состоят из конечного числа предложений вида

С?1 : VI V ... V йк ^к *— : /¿1 Л ... Л Е1 Р'П где Gi тл Fj ~ логические формулы, а щ и ^ — подинтервалы отрезка [0,1]. Содержательно, такое предложение означает, что если вероятность каждой формулы лежит в интервале то вероятность хотя бы одной из формул лежит в интервале щ. Программы без дизъюнкций в головах назовем р-программами. Программа называется простой, если все формулы в ее предложениях являются атомами. В пункте 5.2.2 описана семантика "возможных миров" для этого класса программ, в которой вероятность формулы равна сумме вероятностей миров, в которых эта формула истинна. Моделями программы являются такие распределения вероятностей формул, на которых выполнены все ее предложения. В пункте 5.2.3 доказывается ИР-полнота проблемы совместности (существования модели) и проблемы следования для сопрограмм (здесь, в отличие от большинства КР-полных проблем, основную трудность представляет получение верхней оценки)(теоремы 5.1, 5.2). В указанных работах Р.Энга и В.С.Субраманиана для р-программ была определена семантика неподвижной точки. Эта семантика сопоставляла каждому атому программы (интерпретируемому, как случайное событие) интервал возможных вероятностных значений и утверждалось, что она совпадает с семантикой возможных миров. В пункте 5.2.4 устанавливается, что на самом деле семантика неподвижной точки недостаточна для описания всех моделей программ (предложения 5.3, 5.4, 5.5). В параграфе 5.3 получено полное описание множества точечных вероятностей как семантики возможных миров для разных классов вероятностных логических программ. В частности, мы решаем проблему точного описания семантики интервальных вероятностных программ как для класса р-программ, так и для более широкого класса (1р-программ. В теоремах 5.3 и 5.4 и их следствиях приводится явное описание множества точечных моделей, задаваемых ^программами и ¿р-программами как объединения конечного числа /^-мерных параллелепипедов и ДГ-мерных многогранников, соответственно (Ы - число

°Sg R. and Subrahmanian V.S. Probabilistic Logic Programming. // Information and Computation, 101, 2, 1993. P.150-201. Ng R. and Subrahmanian V.S. A Semantical Framework for Supporting Subjective and Conditional Probabilities in Deductive Databases.// Journal of Automated Reasoning, 10, 2, 1993. P. 191-235.

различных фактов в программе). Описан алгоритм непосредственного построения множеств моделей. Предложен также алгоритм СепМос1Т, использующий для построения множества моделей сопрограммы ряд эвристик, позволяющих во многих случаях существенно уменьшить объем перебора. В параграфе 5.4 изучается семантика простых ¿р-программ. Устанавливаются необходимые и достаточные условия для того, чтобы теоретико-модельная семантика простой сопрограммы совпадала с ее семантикой неподвижной точки (теорема 5.7).

Глава 6 посвящена двум теоретическим вопросам, связанным с языком функционального программирования РЕФАЛ (РЕкурсивных Функций Алгоритмический язык), который был создан в 1966 году В.Ф. Тур-чиным в качестве метаязыка для описания семантики других языков. В результате появления достаточно эффективных реализаций на ЭВМ, он стал находить практическое применение в качестве языка программирования. Как язык практического программирования он ориентирован на символьные преобразования. В настоящее время основными диалектами языка являются РЕФАЛ-2 (1970-е), РЕФАЛ-5 (1985) и РЕФАЛ+ (1990), отличающиеся друг от друга деталями синтаксиса и набором дополнительных средств, расширяющих первоначальный вариант.

Первый из рассматриваемых вопросов связан с семантикой языка. Традиционно семантика Рефала определена в его описаниях операци-онно в терминах работы специальной Рефал-машины над основной памятью, называемой полем зрения. Вычисление Рефал-машины основано на правиле самой левой-самой внутренней замены ("вызов по значению"). Как мы выше отмечали, это правило не является правилом вычисления минимальной неподвижной точки, которая представляется естественной семантикой всякой системы рекурсивных определений. В параграфе 6.1 мы выделяем подкласс рекурсивных программ - программы с естественно расширенными базисными функциями, определяющие унарные неконстантные функции, и доказываем в теореме 6.1, что для этого подкласса вызов по значению является правилом вычисления минимальной неподвижной точки. В предложении 6.1 приведены примеры, показывающие, что при нарушении любого из условий теоремы 6.1 ее заключение будет неверно, т.е. все они являются необходимыми для совпадения семантики вызова по значению с семантикой неподвижной точки. В пункте 6.2.3 определено естественное вложение Рефал-программ в класс рекурсивных определений, описанный в теореме 6.1 ( предложение 6.3).Это позволяет заключить, что стратегия вычисления Рефала приводит к вычислению минимальной неподвижной точки (тео-

рема 6.2).В пункте 6.2.4 показано, как, используя различные варианты индукции по неподвижной точке, этот результат можно применить для верификации (доказательства свойств) Рефал-программ.

Параграф 6.3 посвящен оценке сложности одного шага Рефал-машины. На каждом шаге Рефал-машина определяет имя вычисляемой функции Р, ее аргумент ги, а затем, используя определение функции в программе, вычисляет значение и = Р(и>) и заменяет им вызов Р(т) в поле зрения. Если определение замена выполняются весьма эффективно, то при вычислении значения Р(ги) Рефал-машине приходится (вообще говоря, не один раз) решать задачу отождествления некоторого образца V аргумента ^ с ш. В этой задаче аргумент и>, представляет из себя объектное выражение — правильную скобочную последовательность, включающую символы некоторого конечного алфавита и числа, а в образец v, кроме того, могут входить переменные. Теорема 6.3 утверждает, что задача синтаксического отождествления, решаемая на каждом шаге работы Рефал-машины, является ЛГР-полной. Нижняя оценка в этой теореме следует из представляющей самостоятельный интерес леммы 6.1, в которой доказано, что уже для 2-х символьного алфавита задача разрешимости уравнений в словах вида V = ю, в которых переменные входят лишь в левую часть ад, является ЛгР-полной10. Более детальный анализ причин сложности задачи синтаксического отождествления позволил установить для нее верхнюю оценку времени 0((3п2/8)т(к + п)), где к - длина образца, п - длина аргумента и т - число повторяющихся переменных в образце (предложение 6.3). В частности, если ни одна переменная не повторяется, то это дает линейную оценку сложности, а при малом их числе сложность полиномиальна.

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

1) уточнение формулировки проблемы, сокращение ее области определения, выделение легко разрешимых подпроблем;

2) использование эвристических алгоритмов, которые обеспечивают достаточно эффективное и достаточно точное, в том или ином смысле, решение проблемы.

'"Работа автора [8) с этим результатом опубликована в 1933г. При подготовке диссертации я обнаружил ссылку на более раннюю работу Энглуин (Ап^ит) 1980г., посвященную вопросам индуктивного вывода, в которой получен аналогичный результат.

В главе 7 рассматривается еще один подход к эффективному решению трудных проблем — аппроксимируемость на начальных отрезках. Он основан на следующем соображении: если для некоторой проблемы нет алгоритма, который эффективно решал бы ее на всех аргументах, то можно попытаться аппроксимировать ее просто решаемыми проблемами, решения которых совпадают с решениями исходной проблемы для достаточно большого начального отрезка аргументов. При этом оценка практической возможности такой аппроксимации зависит от размера аппроксимирующих алгоритмов как функции от длины отрезков, на которых они дают верные результаты. Так, очевидный "табличный" алгоритм, который можно предложить для быстрого разрешения начального отрезка любой проблемы, имеет экспоненциальный размер от длины аргументов и поэтому не может быть признан эффективным. С другой стороны, существуют сколь угодно сложные проблемы, для которых объем программ, рапознающих за полиномиальное время их начальные отрезки, является медленно растущей функцией от длин отрезков ([1]). Последовательность длин программ, эффективно распознающих начальные отрезки разрешимой проблемы, образует сложностной спектр соответствующей проблемы. Основное внимание в главе 7 уделено аппроксимации "естественных" проблем, полных или трудных в различных сложностных классах. В параграфе 7.2 фиксируются свойства используемой нумерации машин Тьюринга (МТ) и определена сложность М^(АХ) аппроксимации начального отрезка длины х проблемы А, как длина самой короткой программы МТ, распознающей А(у) при у < х за время < /(у). В параграфе 7.3 устанавливается основной технический результат (теорема 7.1): для всякой границы времени / и неубывающей орф а, принимающей все натуральные значения, существует разрешимая проблема А для которой М1 {Ах) совпадает (по порядку) с а(х). Емкостная и временная сложности проблемы А оцениваются через значения а и /. В качестве следствий устанавливается наличие в различных сложностных классах трудно аппроксимируемых проблем. Результаты затем распространяются и на сложность недетерминированных аппроксимаций (теорема 7.2).Связь между аппроксимируемостью и сводимостями с ограниченной сложностью устанавливается в параграфе 7.4. Теорема 7.3 является формализацией следующего содержательного тезиса: если трудно аппроксимируемая проблема А сводится с небольшой сложностью (например, за полиномиальное время) к проблеме В, то и проблема В является трудно аппроксимируемой. Вместе с результатами параграфа 7.3 это позволяет в

параграфе 7.5 получить нижние оценки сложности аппроксимации для проблем, которые являются полными и трудными в различных слож-ностных классах (теоремы 7.4, 7.5, 7.6).В параграфе 7.6 устанавливаются нижние оценки сложности недетерминированной аппроксимируемости (теорема 7.7) и в качестве следствий выводится сверхполиномиальная (экспонециальная) сложность логических схем, реализующих начальные отрезки проблем, которые являются трудными для классов EXPTIME (EXPSPACE). Для некоторых разрешимых логических теорий устанавливаются нижние оценки объема аксиоматических систем, в которых все теоремы ограниченной длины имеют "короткие" доказательства (следствия 7.7.1 и 7.1.2). В частности, если в некоторой системе аксиом любая теорема арифметики Пресбургера длины < п имеет доказательство длины < 2ч/™, то размер этой системы не меньше с" для некоторой константы с > 1, не зависящей от п. Завершается параграф оценками сложности аппроксимации начальных отрезков "понятных", "красивых" теорем трудных теорий (теорема 7.8). Здесь закавыченные понятия понимаются, как формулы, имеющие небольшую сложность порождения (Колмогоровскую сложность), поскольку строки с большой Колмогоровской сложностью естественно считать "случайными", "запутанными" и т.п. В параграфе 7.7 устанавливается связь между полиномиальной аппроксимируемостью и некоторыми свойствами плотности полных и трудных проблем (лемма 7.5).В качестве следствий из результатов предыдущих параграфов получены, а в некоторых случаях и усилены, результаты о плотности полных проблем и сводимости к "редким" множествам из работ П.Бермана (P.Berman), Н. Линч (N. Lynch) и Р. Соловея (R.Solovay) (теорема 7.9, предложения 7.3, 7.4, 7.5).

Параграф 7.8 посвящен установлению связей между границами вычислительной сложности проблемы и ее аппроксимируемостью. Основной здесь является лемма 7.6 об ускорении вычислений проблем с достаточно медленно растущей сложностью аппроксимации. Теорема 7.10 использует эту лемму и позволяет определить по верхней границе h(x) вычислительной сложности проблемы А и нижней границе - д(х) такую функцию Гд^(х), что для сложности аппроксимации f(x) < д{х)/\х\ и для бесконечного числа значений х имеет место неравенство М/{Ах) > [log2 г^д(х)\. Показано, как этот результат можно перенести на временную сложность и приведены примеры функций гд^{х) для различных конкретных h(x) и д(х). Теорема 7.11 дает примеры проблем, для которых нижняя оценка сложности аппроксимации из теоремы 7.10 является почти оптимальной.

Список публикаций автора по теме диссертации

[1] Дехтярь М.И. О сложности аппроксимации рекурсивных множеств //Electronische Informatik und Kibernetik, Akademie Verlag, Berlin, V. 12, N 3, 1976. P. 115-122.

[2] Дехтярь М.И. О полиномиальной аппроксимируемости и сводимости // Четвертая Всесоюзная конференция по математической логике, Кишенев, 1976. С.41.

[3] Dekhtyar M.I. Complexity spectra of recursive sets and approximability of initial segments of complete problems // Electronische Informatik und Kibernetik, V.15, N 1/2, Akademie Verlag, Berlin, 1979. P.ll-32.

[4] Dekhtyar M.I. Bounds on computational complexity and approximability of recursive sets // 8-th Symp. MFCS, Lecture Notes in Computer Science, V. 74, Springer, 1979. P.277-283.

[5] Дехтярь М.И. Об аппроксимируемости и ускоряемости вычислений рекурсивных множеств // Пятая Всесоюзная конференци по математической логике. Тезисы докладов. Новосибирск, 1979. С.40-41.

[6] Дехтярь М.И. О сложности некоторых подтеорий сложных теорий // Семиотика и информатика, вып. 12, М.: ВИНИТИ, 1979. С.144-147.

[7] Дехтярь М.И. О сводимости к "редким"множествам и плотности NP-полных задач // Автоматы, алгоритмы, языки. Сб. трудов. Калининский государственный университет, Калинин, 1982. С.42-52.

[8] Дехтярь М.И. Замечание о сложности задачи синтаксического отождествления для языка рекурсивных функций // Математическая логика, математическая лингвистика и теория алгоритмов. Сб. трудов. Калининский государственный университет, Калинин, 1983. С.27-31.

[9] Дехтярь М.И. Сложность решения одного класса уравнений в словах // Седьмая Всесоюзная конференция по математической логике. Тезисы докладов. Новосибирск, 1984. С.58.

[10] Дехтярь М.И. О семантике Рефал-программ // Сложностные проблемы математической логики. Сб. трудов. Калининский государственный университет, Калинин, 1985. С.36-41.

[11] Дехтярь М.И. О семантике и доказательстве свойств Рефал-программ // Всесоюзная научная конф. Проблемы совершенствования, тестирования, верификации и отладки программ. Тезисы докл., т. 1, Рига, 1986. С. 102-103.

[12] Дехтярь М.И., Диковский А.Я. Динамические дедуктивные базы данных // Известия РАН, Техническая кибернетика, N 5, 1994. С.55-66. (личный вклад 6С.)

[13] Dekhtyar M.I., Dikovsky A.Ja., On Stable Behavior of Dynamic Deductive Data Bases // Proc.of the 10th International Symp. on Logic Programming, Ithaca, USA. The MIT Press, 1994. P.677.

[14] Dekhtyar M. I., Dikovsky A. Ja., Dynamic Deductive Data Bases with Steady Behavior // Proc. of the 12th International Conf. on Logic Programming, (L. Sterling Ed.), The MIT Press, 1995. P.183-197. (личный вклад 7C.)

[15] Дехтярь М.И., Диковский А.Я. EE-стабильность и перспективность поведения динамических дедуктивных баз данных. ИПМ им. М.В.Келдыша РАН, Препринт N 116, 1995. 34 с. (личный вклад 17С.)

[16] Dekhtyar М. I., Dikovsky A. Ja. Properties of steady behavior of dynamic deductive data Bases. Part I. EE-stability and Promise // Universite Paris XII, Technical Report 95-07, 1995. 26р. (личный вклад 13C.)

[17] Dekhtyar M. I., Dikovsky A. Ja. Properties of steady behavior of dynamic deductive data bases. Part II. Homeostaticity. Universite Paris XII, Technical Report 96-09, 1996. 15р. (личный вклад 7C.)

[18] Дехтярь М.И., Диковский А.Я. Анализ поведения дискретных динамических систем средствами логического программирования // Программирование, N 3, 1996. С.3-16.

(личный вклад 7С.)

[19] Dekhtyar М. I., Dikovsky A. Ja. On Homeostatic Behavior of Dynamic Deductive Data Bases // Proc. 2nd Int. A.P.Ershov Memorial Conference "Perspective of Systems Informatics", Lecture Notes in Computer Science, Springer, V. 1181, 1996. P.420-432. (личный вклад 6C.)

[20] Dekhtyar M. I., Dikovsky A. Ja., Recognition of deductive data base stability // Logic. Foundation of Computer Science - 4th International Symposium LFCS'97, Yaroslavl, Lecture Notes in Computer Science, V. 1234, Springer, 1997. P.67-77. (личный вклад 6C.)

[21] Dekhtyar M. I., Dikovsky A. Ja. Total homeostaticity and integrity constraints restorability // Proc. of the 14th International Conference on Logic Programming. The MIT Press, Cambridge, Massachucetts, London, England, 1997. P.241-255. (личный вклад 7C.)

[22] Dekhtyar M., Dikovsky A., Spyratos N. On Conservative Enforced Updates // Proceedings of 4th International Conference, LPNMR'97. Dagstuhl Castle, Germany, Lecture Notes in Computer Science, V. 1265, Springer, 1997. P.244-257. (личный вклад 5C.)

[23] Дехтярь М.И., Диковский А.Я., Спиратос Н. Восстановление ограничений целостности за счет наименьших достаточных изменений // Программирование. N 2. 1998. С.27-37.

(личный вклад 4С.)

[24] Dekhtyar M.I., Dikovsky A.Ja., Spiratos N. On Logically Justified Updates // Proc. of the 1998 Joint International Conf. and Symp. on Logic Programming. Manchester-1998. The MIT Press, 1998. P.250-264. (личный вклад 5C.)

[25] M.I. Dekhtyar, A. Ja. Dikovsky, N. Spyratos. Incremental Expansion of Database Updates through Integrity Constraints // Proc of JFPLC'99, Lyon (France).-Hermes Science Publications, 1999, P. 189-204. (личный вклад 6C.)

[26] Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Monotone Expansion of Updates in Logical Databases // Proc. of 5th International Conference LPNMR'99. Lecture Notes in Artificial Intelligence, V. 1730, Springer, 1999. P. 132-147. (личный вклад 6C.)

[27] Dekhtyar M. I., Dikovsky A. Ja., Valiev M. K. Applying temporal logic to analysis of behavior of cooperating logic programs // Proc. of 3rd Int. A.P.Ershov Memorial Conf. PSI'99, Novosibirsk, July, 1999. Lecture Notes in Computer Science, V. 1755, Springer, 2000. P.228-234. (личный вклад 2C.)

[28] Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Maximal Expansions of Database Updates // Foundations of Information and

Knowledge Systems, FoIKS 2000. Lecture Notes in Computer Science, V. 1762, Springer, 2000, P.72-87. (личный вклад 4C.)

[29] Dekhtyar M., Dikovsky A., Dudakov S. On Complexity of Updates Through Integrity Constraints // Proc. of the First Int. Conf. on Computational Logic (CL 2000), Lecture Notes in Artificial Intelligence, V. 1861, Springer, 2000. P.867-881. (личный вклад 5C.)

[30] Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Maximal State Independent Approximations to Minimal Real Change // Annals of Mathematics and Artificial Intelligence. V. 33, Kluwer Academic Publishers, 2001. P.157-.204. (личный вклад ЮС.)

[31] Валиев М.К., Дехгярь М.И., Диковский А.Я. О сложности поведения систем взаимодействующих агентов// Труды конференции, посвященной 90-летию со дня рождения Алексея Андреевича Ляпунова, Новосибирск, Академгородок, 8 - 11 октября 2001г., С.18-28. (личный вклад 4С.)

[32] Dekhtyar М. I., Dikovsky A. Ja., Valiev М. К. On Behavior of Interacting Agents // Research report N 02.01, March 2002, IRIN, Universite de Nantes, 36 p. (личный вклад 12C.)

[33] Dekhtyar M. I., Dikovsky A. Ja., Valiev M. K. Complexity of MultiAgent Systems Behavior // Proc. of 8th European Conf. on Logics in Artificial Intelligence, JELIA 2002. Cosenza, Italy, Lecture Notes in Artificial Intelligence, V. 2424 , Springer, 2002. P. 125-136. (личный вклад 4C.)

[34] Dekhtyar M. I., Dikovsky A. Ja. Valiev M. K. Checking MultiAgent Systems Behavior Properties // Proc. of IEEE Internat. Conf. on Artificial Intelligence Systems. (ICAIS2002). September 5-10, 2002, Divnomorskoe, Russia, 2002. P.308-313. (личный вклад 2C.)

[35] Дехтярь М.И. Обновления баз данных при динамических ограничениях целостности // "Системная информатика", N 8, Сб. научных трудов под ред. И.В.Поттосина и Ф.Г.Марчука. Новосибирск : Наука. 2002. С.72-142.

[36] Валиев М.К., Дехтярь М.И., Диковский А.Я. О сложности верификации систем взаимодействующих интеллектуальных агентов

// Труды международных конференций "Интеллектуальные систе-мы"(1ЕЕЕЕ AIS'03) и "Интеллектуальный САПР"( CAD2003), Див-номорское, 2-8 сентября 2003, М.: Физматлит, 2003, С. 475-481. (личный вклад 2С.)

[37] Валиев М.К., Дехтярь М.И., Диковский А.Я. О сложности верификации динамических свойств многоагентнтных систем // Труды Первой Всероссийской научной конференции "Методы и средства обработки информации", Московский гос. университет, 2003, С. 329335. (личный вклад 2С.)

f38] Dekhtyar М., Dikovsky A., and Valiev М. On feasible cases of checking multi-agent Systems Behavior // Theoretical Computer Science, Elsievier Science, V. 303, N. 1, 2003. P.63-

81. (личный вклад 6C.)

[39] Dekhtyar A., Dekhtyar M.I. Possible Worlds Semantics for Probabilistic Logic Programs // Proc., International Conference on Logic Programming (ICLP)'2004, Lecture Notes in Computer Science, V. 3132, Springer, 2004. P.137-148. (личный вклад 6C.)

[40] Дехтярь A.M., Дехтярь М.И. О семантике простых логических программ с интервальными вероятностями // Труды Девятой национальной конференции по искусственному интеллекту с международным участием (КИИ-2004), Том 1, Тверь, М.: Физматлит, 2004. С.254-262. (личный вклад 4С.)

[41] Валиев М.К., Дехтярь М.И., Диковский А.Я, Китаев Е. Л., Скороходов А.П. Верификация динамических свойств многоагентных систем // Труды Ш-го Межд. научно-практического семинара "Интегрированные модели и мягкие вычисления в искусственном интеллекте", М.: Физматлит, 2005. С.69-75. (личный вклад 2С.)

[42] Dekhtyar A., Dekhtyar M.I. Revisiting the Semantics of Interval Probabilistic Logic Programs // Proc. 8th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'05), Lecture Notes in Artificial Intelligence, V. 3662, Springer, 2005. P.330-342. (личный вклад 6C.)

[43] Dekhtyar M.I., Dikovsky A.Ja., Valiev M.K. On complexity of verification of interacting agent's behavior // Annals of Pure

and Applied Logic, V. 141, Elsevier, 2006. P.336-362. (личный вклад 9C.)

[44] Валиев M.K., Дехтярь М.И., Диковский А.Я. О свойствах много-агентных систем с вероятностными каналами связи // Труды IV-ой Межд. научно-практической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте", М.: Физмат-лит, Коломна, 2007. С.119-126. (личный вклад ЗС.)

[45] Dekhtyar M.I., Dikovsky A.Ja., Valiev M.K. Temporal Verification of Probabilistic Multi-Agent Systems // Pillars of Computer Science: Essays Dedicated to Boris (Boaz)Trakhtenbrot on the Occasion of His 85th Birthday, Lecture Notes in Computer Science, V. 4800, Springer, 2008. P.256-265. (личный вклад ЗС.)

[46] Дехтярь A.M., Дехтярь М.И. О семантике дизъюнктивных логических программ с интервальными вероятностями // Труды XI Национальной конференции по искусственному интеллекту с международным участием. Дубна, M.:"LENAND", 2008. С.240-248. (личный вклад 4С.)

[47] М.К. Валиев, М.И. Дехтярь. Вероятностные мультиагент-ные системы: семантика и верификация // Вестник Тверского государственного университета, серия "Прикладная математика". 35 (95), 2008. С.9-22. (личный вклад 7С.)

[48] Dekhtyar A., Dekhtyar M.I. The Theory of Interval Probabilistic Logic Programs // Annals of Math, and Art. Intel., 2009. 32р. (принято в печать), (личный вклад 16С.) http://www.springerlink.com/content/8n82m5637028489v/ ?p=5a24db81e09a4234907d44a4de6e066e&pi=18

[49] Валиев М.К., Дехтярь М.И., Диковский А.Я. Системы агентов, управляемых логическими программами: сложность верификации // Программирование, 5, 2009. 22с. (принято в печать) (личный вклад 8С.)

Технический редактор А.В. Жильцов Подписано в печать 02.10.2009. Формат 60 х 84 Viв-Усл. печ. л. 2,25. Тираж 100 экз. Заказ № 401. Тверской государственный университет Редакционно-издательское управление Адрес: Россия, 170100, г. Тверь, ул. Желябова, 33.

Тел. РИУ: (4822) 35-60-63.

35

Введение

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.1 Поведение дискретных интерактивных систем.

3.2 Дедуктивные базы данных с обновлениями.

3.2.1 Логические программы с обновлениями: синтаксис

3.2.2 Логические программы с обновлениями: семантика

3.2.3 Классы ДБД и алгоритмические проблемы.

3.2.4 Примеры.

3.3 Сложность проблемы перспективности

3.4 Сложность проблемы стабильности

3.4.1 33-стабильность

3.4.2 VQ-стабильность.

3.4.3 3V—стабильность.

3.5 Сложность проблемы гомеостатичности

3.6 Сложность тотальной гомеостатичности.

4 Анализ поведения мультиагентных систем

4.1 Агенты и мультиагентные системы.

4.1.1 Архитектура и семантика МА-систем типа IMPACT

4.1.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 Верификация динамических свойств MAC

5 Семантика логических программ с интервальными вероятностями

5.1 Введение.

5.2 Интервальные вероятностные логические программы

5.2.1 Синтаксис.

5.2.2 Семантика возможных миров.

5.2.3 Пробпема совместности.

5.2.4 Семантика неподвижной точки и ее недостаточность

5.3 Семантика возможных миров: описание и вычисление

5.3.1 Модели dp-программ.

5.3.2 Простые dp-программы: характеризация моделей

5.3.3 Простые dp-программы: явное вычисление моделей

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 Нижние оценки аппроксимируемости трудных проблем.

Общая характеристика работы

Актуальность. Диссертация посвящена исследованию семантических проблем и анализу сложности алгоритмических проблем в таких областях теоретической информатики как дедуктивные базы данных, мультиагент-ные системы, языки функционального и логического программирования. Многие из рассматриваемых в работе тем традиционно относят также к области искусственного интеллекта, поскольку рассматриваемые системы — активные базы данных, динамические дедуктивные базы данных и муль-тиагентные системы — демонстрируют черты разумного поведения. Все указанные области имеют не очень длинную историю (впрочем, как и вся теоретическая информатика), достаточно активно развиваются в последние десятилетия и являются вполне актуальными и в настоящее время. Это подтверждается, в частности, все возрастающим числом научных журналов и международных конференций, тематика которых включает перечисленные выше области.

Появление логического программирования обычно связывают с именами Дж. Робинсона, предложившего в 1965г. правило логического вывода, получившее название метода резолюций, Р. Ковальского, показавшего в начале 70-х, как на этом методе можно построить язык программирования, М. ван Эмдена. А. Колмероэ и Д. Уоррена, внесших в середине 70-х большой вклад в практическую реализацию языка Пролог. В те же годы методы автоматического вывода активно разрабатывались в Ленинградский логической школе. Предложенный С.Ю.Масловым "обратный метод вывода" был, по-существу, эквивалентен методу резолюции.

Логические программы применяются в различных системах, основанных на знаниях. Они могут выступать в качестве языка запросов для реляционных баз данных, представлять интенсиональные компоненты дедуктивных баз данных, использоваться для вывода заключений в экспертных системах. В настоящей работе присутствуют четыре подхода к использованию логического программирования: во 2-ой главе логические программы задают ограничения целостности для транзакций и состояний в полных (реляционных) и частичных базах данных, в 3-ей главе логические программы с обновлениями определяют поведение динамических дискретных систем - осуществляют изменения их состояний, в 4-ой главе они выступают в качестве основных компонент интеллектуальных агентов, отвечающих за определение их возможных действий. Наконец, в 5-ой главе мы изучаем логические программы с интервальными вероятностями, которые используются для представления и вывода неточных знаний о фактах и событиях.

Вопросы интеллектуального выполнения внешних запросов на обновление в базах данных (БД) и базах знаний (БЗ), непрерывно поддерживающих ограничения целостности (ОЦ), исследовались с начала 80-х годов для класса пропозициональных БЗ. Первые шаги по формализации обновлений БЗ были предприняты П. Гарденфорсом (Gardenfors Р.) и его коллегами, которые предложили некоторый набор постулатов, описывающих обновления БЗ при появлении новых знаний. Позже X. Катсуно (H.Katsuno) и А. Мендельзон (A. Mendelzon) [136] уточнили эти постулаты для пропозиционального случая. Их аксиомы неявно выражают важный принцип минимальных изменений, выполняемых в исходных моделях для получения результирующих. В каждом конкретном случае операторы обновления определяются с помощью некоторого явного критерия близости двух моделей. Такие критерии были предложены в работах Ю. Деяла (U.Dayal), К.Форбуса (Forbus К.) и других авторов. В большинстве работ расстояние между двумя моделями оценивалось через мощность их симметрической разности. В случае логики 1-го порядка ситуация с обновлениями БД и БЗ усложняется из-за возможности различных конструктивных интерпретаций отрицания. Целый ряд семантик отрицания был предложен в работах К. Апта (К. Apt), Н. Бидуа (N. Bidoit), ван Гельдера (van Gelder), Т. Пжимужинского (Т. Przymusinski), М.Гельфанда и В. Лифшица и др. Большинство авторов сосредотачивались на обновлениях БЗ. В этой области можно выделить работы X. Алфереса (J. Alferes) и Л.Перейры (L. Pereira)[61], С. Чери (S. Ceri) (J.Widom) [75], Т. Пжимужинского и X. Тернера (H.Turner) [169], Т. Айтера (Т. Eiter) и Г. Готлоба (G. Gottlob) [116] и др. В некоторых подходах при обновлениях изменяется не только БД, но и интенсиональная компонента БЗ. Кроме того, общей чертой предлагаемых методов обновления БЗ является то, что в качестве возможных результатов рассматриваются только специальные (минимальные, wf-, совершенные, стабильные и др.) модели. Это вполне оправдано для систем с интенсиональными знаниями. Однако этот подход не применим к БД, где ОЦ не должны изменяться и любая их модель является допустимой. Работа [156] представляет собой обзор около 20 методов поддержания ограничений целостности и выполнения обновлений. Большинство из них относятся к обновлениям представлений (views) баз данных. Различия рассмотренных методов связаны как с различными средствами задания схем БД, представлений, ограничений целостности и обновлений, так и с разными механизмами выполнения обновлений. Проблема наименьших допустимых обновлений для БД была рассмотрена Н. Спиратосом (N. Spyratos) с соавторами [128, 144] для очень простого подкласса ограничений целостности - правил вида I 1\. . Отталкиваясь от этой работы, мы исследовали ее в более общих случаях.

В области динамических (дедуктивных) баз данных с обновлениями (ДБД) внимание в первую очередь было уделено средствам задания обновлений, анализу их выразительных возможностей и сложности. Здесь можно отметить монографию [190] и исследования С. Абитбуля (S. Abiteboul) [60], А. Боннера (A.Bonner) и М. Кифера (М. Kifer) [69, 70], С. Манчанры (S. Manchanda) и Д. Уоррена (D. Warren)[153] и др. (см. [166, 172, 189|). При этом обновления, нарушающие ОЦ, как правило, считались недопустимыми. Мы в главе 3 снимаем это ограничение и рассматриваем ДБД как интеллектуального агента, взаимодействующего со внешней средой, и при этом действия каждой из сторон могут нарушать ОЦ.

Понятие интеллектуального агента сейчас является, пожалуй, основным в искусственном интеллекте (ИИ). Например, на нем построено все изложение в классическом учебнике С.Рассела и П.Норвига [52]. Исследования систем взаимодействующих интеллектуальных агентов занимают одно из ведущих мест в области ИИ и прикладного программирования. В первую очередь это объясняется тем, что мультиагентные системы (МА-системы) имеют широкую сферу применений, включающую такие разные области как управление бизнес-процессами, электронная торговля, Интернет-навигация, социальные и военные приложения и др. Такое разнообразие приложений привело к появлению многочисленных различных подходов к определению понятий агента и МА-системы (использующих, к тому же, разные уровни абстракции от конкретных систем). Среди авторов основных концепций и посвященных МА-системам монографий выделим М.Вулдриджа ( M.Wooldridge) и Н.Дженнингса (N. Jennings) [188], А. Pao (A.Rao) и М. Джорджефа (M.Georgeff) [171], B.C. Субраманиана (V. S. Subrahmanian) с соавторами [180], И. Шохама (Y.Shoham) и К. Лейтон-Брауна (K.Leyton-Brown) [176]. Отметим также достаточно обширные обзоры на русском языке В.И. Городецкого и Д.А. Поспелова [15, 16. 51] и монографию В.Б. Тарасова [53], в которых рассмотрены многочисленные предложенные модели, а также промышленные инструментальные средства, предназначенные для реализации МА-систем.

Рассматриваемая нами проблема верификации МА-систем, относится к классу проблем, который под названием model checking (проверка на моделях программ) изучается уже ряд лет для абстрактных систем (диаграмм) переходов и конкретных программных систем. Содержательно, они формулируются так: по спецификации динамической системы (программы) определить, выполняется ли для нес некоторое свойство, выраженное в некотором формальном языке (как правило, языке какой-либо временной логики). Началом исследований в этой области послужили работы Б. Кларка (E.Clarke) с Е. Эмерсоном (E.Emerson) и Ж.-П. Квайла (J.-P.Queille) с Дж. Сифакисом (J.Sifakis) в начале 80-х, которые были продолжены М. Варди (M.Vardi), П. Вольпером (P. Wolper), Д. Пеледом (D. Peled), О. Купферман (O.Kupferman) и др. Они были подытожены в классической монографии [79]. Современное состояние области отражено в монографии К. Байера (C.Baier) и Ж-П. Катоена (J-P. Katoen) [65]. В частности, в нее вошли результаты К.Куркубетиса (C.Courcoubetis) и М.Янакакиса (M.Yannakakis) по алгоритмам верификации вероятностных систем, которые мы используем при верификации вероятностных МА-систем в параграфе 4.4.

Отметим, что в разных областях ИИ постоянно возрастает интерес к исследованию систем, включающих стохастические элементы. Одна из таких областей — вероятностные базы знаний. Для задания их интенсиональной компоненты используются разные варианты вероятностного логического программирования. Они рассматривались в работах Д.Пула (D.Poole) [168], Л.Нго (L.Ngo) и П.Хаддави (P.Haddawy) [163], К. Барала (C.Baral), М. Гельфонда и Д.Раштона ( J.Rushton) [66].

В ряде случаев бывает трудно точно оценить вероятность тех или иных фактов или событий. Тогда используют интервалы вероятностей, которые являются ограничениями для множества возможных истинных точечных вероятностных распределений. Несколько вариантов вероятностного логического программирования, основанное на Баейсовском подходе, определил и изучал Лукашевич (Lukasiewicz) [149, 150]. В его программах интервальное правило вида (H\B)[ci: С2] означает, что с\Р(В) < Р(НЛВ) < с2Р(В). Другой подход, основанный на вероятностной выполнимости (PSAT) берет свое начало в работе Буля по теории вероятностей [71]. В ней он рассматривал конечное множество пропозициональных формул F\,., Fm над множеством атомов Аь . . Ап и предполагал, что вместо знаний об истинности или ложности формул известны их вероятности Prob(Fi) = pi, 1 < г < т. Буля интересовало можно ли так назначить вероятности Prob(Aj) — qj, 1 < j < п, пропозициональным атомам, чтобы все утверждения о вероятностях формул F\,., Fm оказались верны. Этот подход естественным образом переносится на интервальные вероятности. Основанные на нем формализмы логических программ с интервальными вероятностями были предложены в работах Р.Энга (R.Ng) и В.С.Субраманиана (V.S.Subrahmanian) [161, 162] В. Лакшманана (V.Lakshmanan) и Ф.Садри (F. Sadri) [143, 142]. Семантика интервальных вероятностных программ задается с помощью множества возможных миров, в которых для каждого события известно, произошло оно или нет. Вероятность события есть сумма вероятностей всех миров, в которых событие произошло. В работах [161, 162] для рассматриваемого класса программ была также предложена семантика, основанная на вычислении минимальной неподвижной точки рекурсивного определения, задаваемого программой, и содержалось утверждение о совпадении этих двух семантик. В главе 5 эю утверждение уточняется и дается точное описание семантики вероятностных логических программ.

Вообще семантика рекурсивных определений вызывает постоянный интерес, поскольку рекурсия является одним из самых мощных средств разработки программ как в традиционных императивных языках программирования, так и в языках логического и функционального программирования, где она является основным таким средством. Многие результаты о рекурсивных программах собраны в книге 3. Манны (Z.Manna) [47]. В ней различные вычислительные стратегии оцениваются по отношению к вычислению семантики наименьшей неподвижной точки. В частности, показано (с ссылкой на диссертацию Морриса [159]), что правило самой левой-самой внутренней замены ("вызов по значению ") не является правилом вычисления неподвижной точки для класса всех рекурсивных программ. В то же время это правило используется в операционной семантике некоторых языков программирования. В частности, с его помощью определена семантика языка Рефал. Этот язык функционального программирования был создан В. Турчиным в 1966 году и успешно развивается уже более 40 лет им самим и группами его учеников в Москве, Нью-Йорке и Переславле Залесском. Поэтому естественно возникла задача выделения класса рекурсивных программ, для которых правило вызова по значению вычисляет наименьшую неподвижную точку и выяснения отношения Рефал-прогамм к этому классу. Еще одна проблема, связанная с языком Рефал, — это сложность выполнения одного шага Рефал-машиной.

Как мы уже отмечали, алгоритмические и сложностные проблемы, наряду с семантическими, занимают центральное место в нашей работе. Классическая теория алгоритмов занималась классификацией алгоритмических проблем на разрешимые и неразрешимые, уделяя основное внимание последним (см. [57]). С появлением и развитием вычислительной техники алгоритмы заняли одно из важнейших мест как в практике вычислений, так и в в науке о них — информатике (computer science). В выдержавшей уже три издания книге Д. Харела (D. Harel) [130] с говорящим названием "Algorithmics: the spirit of computing" утверждается: "Алгоритмика — это больше, чем ветвь информатики. Она является ядром информатики и, со всей определенностью можно сказать, имеет важное значение для большинства наук, бизнеса и технологии." Появившаяся в 60-х годах XX века теория сложности алгоритмов и вычислений — сосредоточилась на классификации и изучении сложности разрешимых проблем. Ее "окончательная" цель состоит в определении сложности любой корректно сформулированной задачи. Другие цели связаны с установлением и пониманием отношений между различными вычислительными феноменами. Наибольших успехов теория добилась как раз в достижении этих целей. Многие результаты по сложности вычислений приведены в учебнике Пападимитриоу (C.Papadimitriou) [164] и вошли в недавние монографии [80. 124, 132, 139].

Прежде всего нужно отметить выделение классов Р и NP задач, разрешимых за полиномиальное время детерминированными и недетерминированными алгоритмами, соответственно. Класс Р считается формализацией содержательного понятия "практически разрешимой задачи". Хотя вопрос о совпадении или различии этих классов "Р = NPT1 остается нерешенным, обнаружение в последние 38 лет многочисленных АГР-полных проблем (в том числе и в данной работе) позволило связать между собой задачи в совершенно различных областях информатики и математики (см. [17]). Кроме того, для многих конкретных алгоритмических проблем разными авторами была установлена полнота в больших сложностных классах PSPACE, EXPTIME и др.

Еще одно направление в теории сложности — сложность алгоритмов или "информационная" сложность — получило начало в работах А.Н.Колмогорова. А.А.Маркова и их учеников2. Здесь изучаются размеры (длины) программ, решающих соответствующую алгоритмическую проблему, при отсутствии или наличии некоторых ограничений на сложность (время, память) вычислений. Сложностью М^(АХ) аппроксимации начального отрезка длины х проблемы А мы называем длину самой короткой программы,

Формально этот вопрос был поставлен С. Куком в 1971г. [81], но его содержательная постановка в терминах сложности доказательств была сделана К.Геделем в письме фон Нейману в 1956г. (см. [80]).

23а рубежом независимо тот же подход был предложен Р. Соломоновым (R. Solomonoff) и Г.Чейгиным (G.Chaitin). распознающей А{у) при у < х за время < f(y). Наши результаты о сложности аппроксимации были получены в конце 70-х годов. За рубежом исследования связи между колмогоровской и вычислительной сложностью продолжались в работах Р. Бука (R.Book), Ю. Хартманиса (J.Hartmanis), Д. Лутца (J.Lutz) м др. В частности, недавно были обнаружены неожиданные связи между ограниченной колмогоровской сложностью и и размерностью Хаусдорфа в геометрии фракталов. Среди отечественных авторов имеющих серьезные достижения в теории сложности алгоритмов и вычислений отметим: А.ГТ. Вельтюкова, Н. К. Верещегина, Д.Ю. Григорьева, Ю.В. Матиясевича, А.А. Разборова, А.Л. Семенова, А.О. Слисенко.

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

1) Проблема корректного выполнения обновлений полных (реляционных) и "частичных" баз данных с сохранением статических и динамических ограничений целостности.

2) Разработка моделей дискретных динамических систем, основанных на логических программах с обновлениями, и анализ устойчивого поведения таких систем во взаимодействии с внешней средой.

3) Разработка моделей детерминированных и недетерминированных муль-тиагентных систем и верификация динамических свойств поведения таких систем.

4) Разработка моделей вероятностных мультиагентных систем и анализ их поведения.

5) Исследование сем антик языка дизъюнктивных логических программ с интервальными вероятностями и алгоритмов их вычисления.

6) Семантика и верификация программ языка функционального программирования Рефал и анализ сложности его вычислений.

7) Построение теории аппроксимации алгоритмических проблем на начальных отрезках и исследование сложности аппроксимации полных и трудных проблем в различных сложностных классах.

Методы исследования. В диссертации используются методы таких разделов теоретической информатики как теория баз данных, логическое программирование, теория сложности алгоритмов и вычислений, искусственный интеллект, а также математических дисциплин: математической логики и теории алгоритмов.

Апробация работы Содержание диссертации докладывалось на многих отечественных и международных конференциях и симпозиумах. Среди них выделим Всесоюзные конференция по математической логике (1976,1979, 1984), международные конференции по логическому программированию ICLP (1994, 1995, 1997, 1998, 1999, 2004), международные конференции по логическому программированию и немонотонному выводу LPNMR (1997, 1999, 2005), национальные конференции по искусственному интеллекту с международным участием (КИИ) (2004. 2006, 2008). международные конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте"(2003, 2005, 2007, 2009). Результаты диссертации также докладывались автором на семинарах в ряде отечественных и зарубежных университетов.

Структура и содержание диссертации

Диссертация состоит из введения, семи глав основной части, заключения и списка литературы.

1. Агафонов В.Н., Сложность алгоритмов и вычислений 1.: Новосибирск,НГУ, 1975. 146 с.

2. Агафонов В.Н., Борщев В.В., Воронков А.А. Логическое программирование в широком смысле (обзор)// В кн. Логическое программирование. М.: Мир, 1988. С.298-366.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.:Мир, 1979. 536с.

4. Базисный Рефал и его реализация на вычислительных машинах. // М.: ЦНИПИАСС,У, 40, 1977. 258 с.

5. Барздинь Я.М. Сложность программ, распознающих принадлежность натуральных чисел, не превышающих п рекурсивно-перечислимому множеству // Доклады АН СССР, 182, 6, 1968, С.1249-1252.

6. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах. М.: Физматлит, 2004,704 С.

7. Валиев М.К., Дсхтярь М.И., Диковский А.Я. О сложности поведения систем взаимодействующих агентов// Труды конференции, посвященной 90-летию со дня рождения Алексея Андреевича Ляпунова, Новосибирск, Академгородок, 8-11 октября 2001г., С. 18-28.

8. Валиев М.К., Дехтярь М.И., Диковский А.Я. О сложности верификации динамических свойств многоагентнтных систем // Труды Первой Всероссийской научной конференции "Методы и средства обработки информации", Московский гос. университет, 2003, С. 329-335.

9. М.К. Валиев, М.И. Дехтярь. Вероятностные мультиагентные системы: семантика и верификация // Вестник Тверского государственного университета, серия "Прикладная математика". 35 (95), 2008, С.9-22.

10. Гасфилд Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. СПб.: Невский диалект; БХВ Петербург, 2003. 654 С.

11. Городецкий В.И. Многоагентные системы: современное состояние исследований и перспективы применения// Новости искусственного интеллекта. №1, 1996. С.44-59.

12. Городецкий В.И. Многоагентные системы: основные свойства и модели координации поведения // Информационные технологии и вычислительные системы. №1, 1998. С.22-34.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982, 416с.

14. Дехтярь A.M., Дехтярь М.И. О семантике простых логических программ с интервальными вероятностями // Труды IX национальной конференции по искусственному интеллекту с международным участием (КИИ-2004), Том 1, Тверь, М.: Физматлит, 2004. С.254-262.

15. Дехтярь A.M., Дехтярь М.И. О семантике дизъюнктивных логических программ с интервальными вероятностями // Труды XI Национальной конференции по искусственному интеллекту с международным участием. Дубна, М.: "LENAND", 2008. С.240-248.

16. Дехтярь М.И. О сложности разрешения формул с ограниченными кванторами // III Всесоюзная конференция по математической логике. Тезисы докладов. Новосибирск, 1974. С.58-59.

17. Дехтярь М.И. С сложности аппроксимации рекурсивных множеств // Electronische Informatik unci Kibemetik, Akademie Verlag, Berlin, V. 12, N 3, 1976. P. 115-122.

18. Дехтярь М.И. О полиномиальной аппроксимируемости и сводимости./ / Четвертая Всесоюзная конференция по математической логике, Кишенев, 1976. С.41.

19. Дехтярь М.И. Об аппроксимируемости и ускоряемости вычислений рекурсивных множеств // Пятая Всесоюзная конференци по математической логике. Тезисы докладов. Новосибирск, 1979. С.40-41.

20. Дехтярь М.И. О сложности некоторых подтеорий сложных теорий // Семиотика и информатика, вып. 12, М.: ВИНИТИ, 1979. С.144-147.

21. Дехтярь М.И. О сводимости к "редким"множествам и плотности NP-полных задач // Автоматы, алгоритмы, языки. Сб. трудов. Калининский государственный университет, Калинин, 1982. С.42-52.

22. Дехтярь М.И. Сложность решения одного класса уравнений в словах // Седьмая Всесоюзная конференция по математической логике. Тезисы докладов. Новосибирск, 1984. С.58.

23. Дехтярь М.И. О семантике Рефал-программ // Сложностные проблемы математической логики. Сб. трудов. Калининский государственный университет, Калинин, 1985. С.36-41.

24. Дехтярь М.И. О семантике и доказательстве свойств Рефал-программ // Всесоюзная научная конф. "Проблемы совершенствования, тестирования, верификации и отладки программ". Тезисы докл., т.1, Рига, 1986. С. 102-103.

25. Дехтярь М.И., Дпковский А.Я. Динамические дедуктивные базы данных // Известия РАН, Техническая кибернетика, N 5, 1994. С.55-66.

26. Дехтярь М.И., Диковский А.Я. ЕЕ-стабилыюсть и перспективность поведения динамических дедуктивных баз данных. ИПМ им. М.В.Келдыша РАН, Препринт N 116, 1995. С.1-34.

27. Дехтярь М.И., Диковский А.Я. Анализ поведения дискретных динамических систем средствами логичекого программирования // Программирование, N 3, 3 996. С.3-16.

28. Дехтярь М.И., Диковский А.Я., Спиратос Н.: Восстановление ограничений целостности за счет наименьших достаточных изменений // Программирование. N 2. 1998. С.27-37.

29. Дехтярь М.И. Обновления баз данных при динамических ограничениях целостности // "Системная информатика", N 8, Сб. научных трудов под ред. И.В.Поттосина и Ф.Г.Марчука. Новосибирск.: Наука. 2002. С.72- 142.

30. Дехтярь М.И. Лекции по дискретной математике: учебное пособие. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. 259 с.

31. Диковский А.Я. Алгоритмы линейной сложности для задач, связанных с автоматическим синтезом ациклических программ // Программирование, 3, 1985.

32. Дудаков С.М. Сложность обновлений дедуктивных баз данных с фиксированным ограничением целостности // Вестник Тверского государственного университета, 2, 2003. С.16-27.

33. Дурнев В.Г. К проблеме разрешимости уравнений с одним коэффициентом // Мат. заметки, 59, вып. 66, 1996. С.832-842.

34. Звонкин А.К., Левин Л.А. Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов // Успехи матем. наук, 25, N 6, 1970. С.85-127.

35. Канович М.И. О сложности перечисления и разрешения предикатов // Доклады АН СССР, 192, 4, 1970. С.721-723.

36. Климов Ан. В., Романенко С. А., Турчин В. Ф. Компилятор с языка Рефал. М.: ИПМ АН СССР, 1972. 74 с.

37. Колмогоров А.Н. Три подхода к определению понятия "количество информации"// Пробл. передачи информации, 1, 1965. С.3-11.

38. Т.Кормеи, Ч.Лейзерсон, Р.Ривест. Алгоритмы(построение и анализ). М.: МЦНО. 1999. 955 с.

39. Левин Л.А., Универсальные задачи перебора // Проблемы передачи информации, 9, 1973. С.115-116.

40. Майн X., Осаки С. Марковские процессы принятия решений М: «Наука», Гл. ред. физ-мат. литературы, 1977. 176 с.

41. Маканин Г. С. Проблема разрешимости уравнений в свободной полугруппе // Математический сборник, 103,N 2, 1977. С.147-236.

42. Манна 3. Теория неподвижной точки программ // Кибернетический сборник, вып. 15, М.:Мир, 1978. С.38-100.

43. Марков А.А., О нормальных алгорифмах, вычисляющих булевы функции // Доклады АН СССР, т. 157, N 2, 1964. С.262-264.

44. Мейер Д. Теория реляционных баз данных. М: Мир, 1987. 608 с.

45. Петри Н.В., Сложность алгорифмов и время их работы // Доклады АН СССР, т. 186, N 1, 1969. С.30-33.

46. Поспелов Д.А. Многоагентные системы настоящее и будущее// Ин-форм. технологии и вычислительные системы, №1, 1998. С.14-21.

47. Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд. М.: Изд. дом "Вильяме", 2006. 1408 с.

48. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям. М.: Эдиториал УРСС, М., 2002.

49. Трахтенброт Б.А., Сложность алгоритмов и вычислений. Новосибирск, НГУ, 1967. 258 с.

50. Турчин В. Ф. Метаязык для формального описания алгоритмических языков // Цифровая вычислительная техника и программирование. М.: Сов. Радио, 1966. С. 116-124.

51. Турчин В. Ф. Программирование на языке Рефал. М.: ИПМ АН СССР, препринты N 41, N 43, N 44, N 48, N 49, 1971.

52. Успенский В.А., Семенов A.JI. Теория алгоритмов: основные открытия и приложения. М.: Физматлит, 1987. 288 с.

53. Фрейдзон Р.Т. Регулярная аппроксимация рекурсивных предикатов // Записки научных семинаров Ленинградского отд. Матем. ин-та АН СССР, 20, 1971. С.220-223.

54. С.Чери, Г.Готлоб, Л.Танка. Логическое программирование и базы данных. М.: Мир, 1992. 352 с.

55. Abiteboul S.:Updates a new Frontier // Proc. of the Second International Conference on the Theory of Databases, ICDT'88. Lecture Notes in Computer Science. V. 326, 1988. P. 1-18.

56. Alferes J.J.,Pereira L.M.: Update-Programs Can Update // Second International Workshop, NMELP'96. Selected Papers. Lecture Notes in Computer Science, V.f 1216, 1997. P.110-131.

57. Angluin D. Finding patterns common to a set of strings // Journ. Computer and System Sci., v. 21, N 1, 1980. P.46-62.

58. Apt K. R. Logic Programming // Handbook of Theoretical Computer Science. Formal Models and Semantics, Chapter 10, Elsevier Science Publishers, 1990. P.493-574.

59. Apt K.R., Blair H., Walker A. Towards a theory of declarative knowledge // Foundations of deductive databases и logic programming. Morgan Kaufman Pub., Los Altos, 1988. P.89-148.

60. Baier C., Katoen J-P. Principles of model checking. MIT Press, 2008. 975 p.

61. Baral C., Gelfond M, Rushton J.M. Probabilistic Reasoning With Answer Sets. // Proc. LPNMR-2004, 2004. P.21-33.

62. Bonner A.J. Hypothetical Datalog: complexity and expressibility // Theoretical Computer Science, 76, 1990. P.3-51.

63. Bonner, A.J., Kifer, M. An Overview of Transaction Logic // Theoretical Computer Science, v. 133 (2), 1994. P.205-265.

64. Boole G. An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities. London: Macmillan, 1854.

65. Bordini R., Fisher M., Pardavila C., and Wooldridge M. Model checking AgentSpeak // Second International Joint Conference on Autonomous Agents and Multiagent Systems, (AAMAS'03), 2003. P.409-416.

66. Ceri S., Widorn J. Deriving incremental production rules for deductive data // Information Systems, V. 19, N 6, 1994. P.467-490.

67. Chandra A. K., Kozen D. C., Stockmeyer L. J. Alternation // J. Assoc. Comput. Mach., 28(1), 1981. P.114-133.77| Chen Z., Toda S The complexity of selecting maximal solutions Information and Computation, 119, N 2, 1995. P.231-239.

68. Chvatal V. Linear Programming. San Francisco: W. Freeman и Co., 1983. 478p.

69. Clarke E.M., Grumberg 0. and Peled D. Model checking, MIT Press, 2000. 314 p.

70. Computational complexity theory./ Rudich S., Wigderson A. eds. American Math. Society, Institute for Advanced Study, 2004. 390 p.

71. Cook S.A., The complexity of theorem-proving procedures // Proc. 3-th Ann ACM Symp. on Theory of Computing, 1971. P.151-158.

72. Cook S.A. Characterization of push-down machines in terms of time-bounded computers // J. of ACM, 18, N 1 , 1971, 4-18.

73. Cordoza E., Lipton R., Meyer A.R., Exponential space complete problems for Petri nets and computative semigroups // Proc. 8-th Ann ACM Symp. on Theory of Computing, 1976, P. 50-54.

74. Courcoubetis C., Yannakakis M. The complexity of probabilistic verification // J. ACM, V. 42, 4, 1995. P.857-907.

75. Dantsin, E., Eiter, T. Gottlob, G., Voronkov, A. Complexity and Expressiveness of Logic Programming // Proc. 12th Annual IEEE Conf. On Comput. Compl. 1997. P.82-101.

76. Dekhtyar A., Dekhtyar M.I. Possible Worlds Semantics for Probabilistic Logic Programs // Intern. Conference on Logic Programming (ICLP)'2004, Lecture Notes in Computer Science, V. 3132, 2004. P. 137-148.

77. Dekhtyar A., Dekhtyar M.I. Revisiting the Semantics of Interval Probabilistic Logic Programs // 8th Intern. Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'05), Lecture Notes in Artificial Intelligence, V. 3662, 2005. P.330-342.

78. Dekhtyar A. and Subrahmanian V.S. Hybrid Probabilistic Programs // Journal of Logic Programming, V. 43, 3, 1999. P. 187-250.

79. Dekhtyar M.I. On the complexity of approximation of recursive sets // Electronische Informationsverarbeitung und Kibernetik, V. 12, 3, 1976. P.115-122.

80. Dekhtyar M.I. Complexity spectra of recursive sets and approximability of initial segments of complete problems / / Electronische Informationsverarbeitung und Kibernetik, v. 15, N 1/2, Berlin: Akademie Verlag, 1979. P. 11-32.

81. Dekhtyar M.I. Bounds on computational complexity and approximability of recursive sets // Proc. 8-th Symp. MFCS. Lecture Notes in Computer Science, V. 74, , Springer-Verlag, 1979. P.277-283.

82. Dekhtyar M.I., Dikovsky A.Ja., On Stable Behavior of Dynamic Deductive Data Bases. // Proc.of the 10th International Symp. on Logic Programming, Ithaca, USA. The MIT Press, 1994. P.677.

83. Dekhtyar M. I., Dikovsky A. Ja., Dynamic Deductive Data Bases with Steady Behavior.// Proc. of the 12th International Conf. on Logic Programming, (L. Sterling Ed.), The MIT Press, 1995. P.183-197.

84. Dekhtyar M. I., Dikovsky A. Ja. Properties of steady behavior of dynamic deductive data Bases. Univ. Paris XII, Technical Report 95-07, 1995. 26p.

85. Dekhtyar M. I., Dikovsky A. Ja., Recognition of deductive data base stability // Logic. Foundation of Computer Science 4th International Symposium LFCS'97, Yaroslavl, Lecture Notes in Computer Science, V. 1234, Springer, 1997. P.67-77.

86. Dekhtyar M. I., Dikovsky A. Ja. Total homeostaticity and integrity constraints restorability // Proc. of the 14th International Conference on Logic Programming. London, England, Cambridge, Massachucetts: MIT Press, 1997. P.241-255.

87. Dekhtyar M., Dikovsky A., Spyratos N. On Conservative Enforced Updates // Proceedings of 4th International Conference, LPNMR'97. Dagstuhl Castle, Germany, Lecture Notes in Computer Science, V. 1265, Springer, 1997. P.244- 257.

88. Dekhtyar M.I., Dikovsky A.Ja., Spiratos N. On Logically Justified Updates. // Logic Programming. Proc. of the 1998 Joint International Conf. and Symp. on Logic Programming. Manchester-1998. The MIT Press, 1998. P.250-264.

89. M.I. Dekhtyar, A. Ja. Dikovsky, N. Spyratos. Incremental Expansion of Database Updates through Integrity Constraints // Proc of JFPLC'99, Lyon. France, 1999, 189-204.

90. Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Monotone Expansion of Updates in Logical Databases // Proc. of 5th International Conference LPNMR'99. Lecture Notes in Artificial Intelligence, V. 1730, Springer, 1999. P.132-147.

91. Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Maximal Expansions of Database Updates. // Foundations of Information and Knowledge Systems, FoIKS 2000. Lecture Notes in Computer Science, V. 1762, 2000, P. 72-87.

92. Dekhtyar M. I., Dikovsky A. Ja., Valiev M. K. On Behavior of Interacting Agents. Research report N 02.01, March 2002, IRIN, University de Nantes, 2002. 36 p.

93. Dekhtyar M. I., Dikovsky A. Ja. Valiev M. K. Checking Multi-Agent Systems Behavior Properties // Proc. of IEEE Internat. Conf. on Artificial Intelligence Systems. (ICAIS2002). September 5-10, 2002, Divnomorskoe, Russia, 2002. P.308-313.

94. Dekhtyar M., Dikovsky A., and Valiev M., On feasible cases of checking multi-agent Systems Behavior // Theoretical Computer Science, Elsievier Science, V. 303, N 1, 2003. P. 63-81.

95. Dekhtyar M.I., Dikovsky A.Ja., Valiev M.K. On complexity of verification of interacting agent's behavior // Annals of Pure and Applied Logic, 141, 2006. P.336-362.

96. Dikovsky A.Ja. On computational complexity of Prolog programs j j Theoretical Computer Science, 119, 1993. P.63-102.

97. Dix J., Nanni M., and Subrahmanian V. S. Probabilistic agent reasoning // ACM Trans, of Computational Logic, 1(2), 2000. P.201- 245.

98. Dudakov S.M. On information content of hard sets // Материалы межд. коиф. по матем. логике, посвященной 90-летию со дня рождения А.И.Мальцева (тезисы докладов). Новосибирск, 1999. С.79-80.

99. Eiter Т., Gottlob, G. On the complexity of propositional knowledge base revision, updates, and counterfactuals // Artificial Intelligence, 57, 1992. P.227-270.

100. Eiter Т., Subrahmanian V. S. Heterogeneous Active agents, III: polynomially implementable agents. Techn. Rept. INFSYS RR-1843-99-07, Inst, fur Informationssysteme, Technische Universitat Wien, A-10-40, Vienna, Austria. 1999.

101. Emerson E. A. Model checking and the mu-calculus // Descriptive Complexity and Finite Models. Proc. of a DIM ACS Workshop, 1996. P.185-214.

102. Fagin R. Halpern J., and Megiddo N. A logic for reasoning about probabilities // Information and Computation, V. 87, N 1-2, 1990. P.78-128.

103. Fernandez J.A., Grant J., Minker J. Model-Theoretic Approach to View Updates in Deductive Databases. // Journ. of Automated Reasoning, V. 17, 1996. P.171-197.

104. Ferrante J., Rackoff C.W., The computational complexity of logical theories. Lect. Notes in Math., N 718, Springer-Verlag, 1979. 244 p.

105. Fisher M.J., Rabin M.O., Super-exponential complexity of Presburger arithmetic j j Complexity of Computation, SIAM-AMS Proc VII, Providence, Rhode Island, 1974. P.27 42.

106. Gelfond M., Lifschitz V. The stable model semantics for logic programming // Proc. of the Fifth Intern. Conf. and Symp. on Logic Programming. Cambridge, MA, MIT Press, 1988. P.1070-1080.

107. Goldreich O. Computational complexity. A conceptual perspective. NY: Cambrige University Press, 2008. 606p.

108. Georgakopoulos G, Kavvadias D, Papadimitriou C.H. Probabilistic Satisfiability // Journal of Complexity, V. 4, 1988. P.l-11.

109. Giordano L., Martelli A., and Schwind C. Verifying communication agents by model checking in a temporal action logic // JELIA 2004, Lecture Notes in Artificial Intelligence 3229, 2004. P.57-69.

110. Hailperin T. Best Possible Inequalities for the Probability of a Logical Function of Events // Amer. Math. Monthly, V. 72, 1965. P.343-359.

111. Halfeld Ferrari Alves M., Laurent D., Spyratos N., Stamate D. Update rules and revision programs // Rapport de Recherche Universite de Paris-Sud, Centre d'Orsay, LRI 1010, 12, 1995. 28p.

112. Hansson H., Jonsson B. A logic for reasning about time and reliability // Formal Aspects of Computing, 6(5), 1994. P.512-535.

113. Iiarel D. Algorithmics: the spirit of computing. 3rd ed. Pearson Education Ltd., 2004. 536p.

114. Hartmanis J., Berman L. On isomorphisms and density of NP and other complete sets // Proc. 8-th Ann ACM Symp. on Theory of Computing, 1976. P.30-40.

115. Hemaspaandra L.A., Ogihara M. The complexity theory companion. Springer, 2002. 370 p.

116. Jenner В., Toran J. The complexity of obtaining solutions for problems in NP and NL // Complexity theory retrospective II. N-Y, Springer-Verlag,1997. P.155-178.

117. Karp R.M. Some bounds on the storage requirements of sequential mashines and Turing machines // J. ACM, V. 14, N 3, 1967. P.478-490.

118. Karp R.M. Reducibility among combinatorial problems // Complexity of Computer Computations, New York: Plenum Press, 1972. P.85-104.

119. Katsuno H., Mendelzon, A. O. Propositional knowledge base revision и minimal change // Artificial Intelligence, V. 52, 1991. P.253-294.

120. Kifer M. and Subrahmanian V.S. Theory of Generalized Annotated Logic Programming and its Applications. // Journal of Logic Programming, 12, 4, 1992. P.335-368.

121. Kozen, D., Results on the Propositional //-calculus // Theoretical Computer Science, V. 27, 1983. P.333-354.

122. Kozen, D. Theory of computation. Springer-Verlag. 2006, 418 p.

123. Kwiatkowska M. Model Checking for probability and time: from theory to practice // Proc. 18th IEEE Symposium on Logic in Computer Science, 2003. P.351-360.

124. Kyburg H.E. Jr. Interval-valued Probabilities // G. de Cooman, P. Walley and F.G. Cozman (Eds.), Imprecise Probabilities Project. http://ippserv.rug.ac.be/documentation/intervalprob/intervalprob.html,1998.

125. Lakshmanan V.S. and Sadri F. Modeling Uncertainty in Deductive Databases // Pioc. Int. Conf. on Database Expert Systems and Applications, (DEXA'94), Athens, Greece. Lecture Notes in Computer Science, V. 856, Springer, 1994, P.724-733.

126. Lakshmanan V.S. and Sadri F. Probabilistic Deductive Databases // Proc. Int. Logic Programming Symp., NY: MIT Press, 1994. P.254-268.

127. Lauren, D., Spyratos, N., Stamate, D. Deterministic enforcement of constraints // Programming and Computer Software 24, 1998. P.71-83.

128. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and it's Application. Springer, 1998. 792p.

129. Lifschitz V. On the semantics of STRIPS // Proc. of the Workshop: Reasoning about Actions и Plans , Timberline, OR, 1987. P. 1-9.

130. Lloyd J.W. Foundations of Logic Programming. Second, Extended Edition. Springei', 1993. 212p.

131. Lobo J., Trajcevski G., Minimal and consistent evolution of knowledge bases// Journ. of Appl. Non-Classical Logics, V. 7, N 1-2, 1997. P.117- 146.

132. Lukasiewicz T. Probabilistic Logic Programming // Proc. of the 13th biennial European Conference on Artificial Intelligence (ECAI 1998), Brighton, UK. J. Wiley & Sons, 1998, P.388-392.

133. Lynch N.A., On reducibility to complex or sparce sets // J. ACM, 22, 3, 1975, P 341-345.

134. Lynch N.A., Complexity-class-encoding sets // J. Сотр. Sist. Sci., V. 13, N 1, 1976. P 110-118. £

135. Manchanda, S., Warren, D.S., A logic-based language for database updates // Foundations of Deductive Databases и Logic Programming, Morgan-Kaufmann, Los Altos, CA, 1988. P.363-394.

136. Mahaney S. Sparse complete sets for NP: Solution of a conjectute of Berman and Hartmanis // Journal of Computer and System Sciences, 25(2). 1982. P.130-143.

137. Marek, V.W., Truszcinsky, M. Revision programming, database updates and integrity constraints // International Conference on Data Base Theory, ICDT, Lecture Notes in Computer Science, V. 893, 1995. P.368-382.

138. Meyer A.R., Weak SIS cannot be decided // Notices Amer. Math. Soc., 19, N 5, 1972. P.598.

139. Minker J., Seipel D. Disjunctive Logic Programming: A Survey and Assessment // Computational Logic: Logic Programming and Beyond, 2002. P.472-511.

140. Morris J.H. Lambda-calculus models of programming languages. Ph.D. thesis. Project MAC. MAC-TR-57, MIT, 1968.

141. Muller, J. P., Architectures and applications of intelligent agents: A survey // The Knowledge Engineering Review, V. 13, N 4, 1998. P.353-380.

142. Ng R. and Subrahmanian V.S. Probabilistic Logic Programming. // Information and Computation, 101, 2, 1993. P.150-201.

143. Ng R. and Subrahmanian V.S. A Semantical Framework for Supporting-Subjective and Conditional Probabilities in Deductive Databases.// Journal of Automated Reasoning, 10, 2, 1993. P. 191-235.

144. Ngo L., Haddawy P. Probabilistic Logic Programming and Bayesian Networks. // Proc. ASIAN-1995, 1995. P.286-300.

145. Papadimitriou C.H. Computational Complexity. Addison-Wesley, 1994. 540 p.

146. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988. 552p.

147. Picouet, Ph., Vianu, V. Expressiveness and Complexity of Active Databases //6th Int. Conf. on Database Theory, ICDT'97. Lecture Notes in Computer Science, V. 1186, 1997. P.155-172.

148. Plandowski, W. An efficient algorithm for solving word equations // Proc. of the Thirty-Eighth Annual ACM Symposium on theory of Computing. Seattle, WA, USA, May 21-23, STOC '06. ACM, NY, 2006. P.467-476.

149. Poole D. (1993). Probabilistic Horn Abduction and Bayesian Networks // Artificial Intelligence, 64(1), P. 81-129.

150. Przymusinski, T.C., Turner, H. Update by Means of Inference Rules // Third Int. Conf. LPNMR'95, Lexington, KY, USA, 1995. P. 166-174.

151. Queille J. P., Sifakis J. Specification and verification of concurrent programs in CESAR //Proc. of the 5th Intern. Symp. on Programming, Lecture Notes in Computer Science, V. 137, 1982. P. 195-220.

152. Reiter R. Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001. 400p.

153. Savitch W.J., Relationship between nondeterministic tape complexities // J. Сотр. Syst. Sci., 4, 1970. P.177-192.

154. Schnorr C.P., The network complexity and Turing mashine complexity of finite functions // Acta Informatica, 7, 1976. P.95-107.

155. Shoham, Y., Agent oriented programming // Artificial Intelligence, 60, 1993. P.51-92.

156. Shoham Y., Leyton-Brown K. Multiagent sistems: algorithmic, game-theoretic, ad logical foundations. NY:Cambrige Univ. Press, 2009, 483p.177| Solovay R., On sets Cook-reducible to sparce sets // SIAM J. Comput., V. 5, N 4, 1976. P.646-652.

157. Stockmeier L.J., Meyer A.R. Word problems requiring exponential time // Proc. 5-th Ann ACM Symp. on Theory of Computing, 1973. P. 1-9.

158. Stockmeier L.J. The complexity of decision problems in automata theory and logic // Proj. MAC Techn. Report, 133, M.I.T., Mass., 1974.

159. Subrahmanian V. S., Bonatti P., Dix J., et al., Heterogeneous agent Systems. MIT Press, 2000. 514p.

160. Vardi M.Y. Automatic verification of probabilistic concurrent finite state programs // Proc. of 26th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1985. P.327-338.

161. Vardi M., Wolper P., An automata-theoretic approach to automatic program verification // Proc. of the IEEE Symposium on Logic in Computer Science, 1986. P.332-344.

162. Vullemin J. Proof techniques for recursive programs, Ph.D. thesis, Computer Science Department, Stanford University, 1973.

163. Walley, P. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, 1991. 720p.

164. Weichselberger, K. The theory of interval-probability as a unifying concept for uncertainty // Proc. 1st International Syrnp. on Imprecise Probabilities and Their Applications, 1999. P.387-396.

165. Wooldridge M., Fisher M., Huget M.-P., and Parsons S. Model Checking Multiagent systems with MABLE // Proc. of the First Intern. Conf. on Autonomous Agents and Multiagent Systems (AAMAS-02), Bologna, Italy, 2002. P.952-959.

166. Wooldridge M., Huget M.-P., Fisher M., and Parsons S. Model Checking Multi-Agent Systems: The MABLE Language and Its Applications // Intern. Journal on Artificial Intelligence Tools, 15(2), 2006. P. 195-225.

167. Wooldridge, M., Jennings N. Intelligent agents: Theory and practice // ' The Knowledge Engineering Review, 10(2). 1995. P.115-152.

168. Zaniolo C. A unified semantics for active and deductive databases // 1st International Workshop on Rules in Database Systems, RIDS'93. Springer 1993. P.271-287.

169. Zaniolo C., Cheri S., Faloutsos C., Snodgrass R.T., Subrahmanian V.S., Zicari R. Advanced database systems. Morgan Kaufmann Publishers, Inc., San Francisco, 1997. 574p.