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

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

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

Появление логического программирования обычно связывают с именами Дж. Робинсона, предложившего в 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]. В его программах интервальное правило вида (HB)[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 ½, 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.