Вычислительная сложность некоторых задач математической логики тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Дудаков, Сергей Михайлович

• Дудаков, Сергей Михайлович
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Дудаков, Сергей Михайлович

Введение

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

1.1 Классы сложности и типы сводимости.

1.2 Логические программы.

2 Сложность параллельности для хорновского фрагмента линейной логики

2.1 Основные понятия лин&йной логики.

2.2 Перестановочность, параллельность и сильная параллельность

2.3 Максимальная параллельность.

3 Сложность обновлений моделей логических программ

3.1 Постановка задачи.

3.2 Определения.

3.3 Сложность задач при фиксированной сигнатуре.

3.3.1 Вспомогательная конструкция: J и Т

3.3.2 Алгоритм построения обновления для хорновских ЛП

3.3.3 Ф — хорновская, А положительно.

3.3.4 Ф — хорновская, А произвольно.

3.3.5 Общий случай.

3.4 Случай нефиксированной сигнатуры.

4 Сложность совершенных моделей пропозициональных логических программ

4.1 Совершенные модели логических программ.

4.2 Определения.

4.3 Структура совершенных моделей.

4.4 Нижняя оценка сложности совершенных моделей

5 О структуре полных множеств для NP и EXP

5.1 Основные понятия и определения

5.1.1 Структурная теория сложности.

5.1.2 Информационная сложность проблем.

5.2 Алгоритмическая сложность и плотность

NP-трудных множеств

5.3 О множествах, сводимых к множествам с большой колмого-ровской сложностью.

Введение диссертации (часть автореферата) на тему «Вычислительная сложность некоторых задач математической логики»

Актуальность

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

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

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

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

Логические программы — широко используемый метод представления знаний. Основные исследования в области логических программ связаны с построением их моделей и с анализом выводимости. Одно из наиболее перспективных применений логических программ — это задание с их помощью ограничений целостности баз данных. При этом актуальная и интенсивно исследуемая в настоящее время в теории баз данных задача обновления базы данных превращается в задачу обновления модели логической программы, сложность которой мы изучается в главе 3.

Еще одна важная задача, связанная с логическими программами, — это построение модели с заранее определенными свойствами. Как известно, логическая программа может иметь несколько моделей, поэтому часто возникает задача сужения множества моделей, а в идеале — выбора одной из них, опираясь на какие-либо естественные свойства. Одним из способов решения этой проблемы может быть использование совершенных моделей, которые предложены Пжимусинским [55]. Недостатком этого приема является то, что не всякая логическая программа имеет совершенную модель. Поэтому возникает задача: определить по заданной логической программе существует ли у нее совершенная модель. Частично данная задача решена в работе [28], а в данной работе в главе 4 мы даем точную оценку сложности и отвечаем на отрытый вопрос из [28].

Наличие большого числа сложно решаемых задач и нерешенность проблемы эквивалентности детерминированных и недетерминированных вычислений подтолкнули к исследованию внутренней структуры полных задач. Появился целый раздел теории алгоритмов — структурная теория сложности, — посвященный именно этим вопросам. Прежде всего, это относится к их плотности и алгоритмической сложности, поскольку, например, при небольшой алгоритмической сложности задачи имеется практически значимый способ ее решения на начальном отрезке с использованием ограниченных ресурсов. В главе 5 мы исследуем сложность начальных отрезков NP-трудных и ЕХР-трудных задач.

Обзор литературы

Те области теории алгоритмов, которым посвящена данная работа, интенсивно развиваются. Ежегодно проводятся десятки конференций и издаются десятки журналов, посвященных применению методов математической логики при решении различных задач информатики, в частности, логического программирования, баз данных и др. В этом кратком обзоре мы, конечно, не можем охватить все источники, темы которых так или иначе связаны с темой диссертации. Здесь мы отметим только те монографии, на определения и результаты из которых мы прямо ссылаемся в работе, и статьи, темы которых непосредственно связаны с темами нашего исследования и его результатами. Более полные библиографии можно найти, например, в [15, 7, б, 19, 46]. Кроме того, большое число библиографий доступно через Интернет, например, по адресам: http://www.Stanford.edu/~iliano/linearbib/llb.html (библиография по линейной логике) и http://www.ессс.uni-trier.de/eccc по структурной теории сложности).

Общей теории вычислимости и алгоритмическим сводимостям посвящена книга [4].

В [33, 52] рассматривается вычислительная сложность различных задач, приводятся определения классов вычислительной сложности, примеры задач полных и трудных для различных классов, дается обзор наиболее существенных сведений о структуре полных множеств.

Линейная логика впервые была предложена Жираром в работе [35]. Там же была высказана идея о связи доказательств в линейной логике с параллельными вычислениями. В [47] доказано, что уже пропозициональная часть линейной логики является алгоритмически неразрешимой и поставлена задача о сложности доказательств в хорновском фрагменте. Канович в [41] показал, что задача выводимости в хорновском фрагменте является NP-полной. Другое доказательство того же факта приведено в [10], из него также следует, что задача остается NP-полной даже над алфавитом из двух символов. В [11] даны определения двух классов последовательностей хорновских импликаций — классы перестановочных и параллельных последовательностей. Для перестановочных последовательностей задача выводимости разрешима за полиномиальное время. Там же предложено полиномиально проверяемое условие перестановочности и доказано, что задача распознавания параллельности является NP-трудной.

Основные концепции логического программирования изложены в [48]. Задача обновления моделей логических программ рассматривалась с конца 80-х годов, но наиболее активно стала изучаться в последние несколько лет в связи с появлением концепции активных баз данных (то есть баз данных, использующих средства искусственного интеллекта при осуществлении обновлений) [20,13, 54]. Изначально интерес такого рода вызывался необходимостью средств усиления выразительности SQL-подобных языков обновления [7]. В [23, 24, 37] предложено использовать логические программы в качестве ограничения целостности баз данных, которые используются для автоматического разрешения конфликтов, возникающих при обновлениях. При обновлениях обычно рассматривается два типа задач [28]. «Оптимистические» — когда достаточно, чтобы существовал способ выполнить обновление с соблюдением некоторых условий, — и «пессимистические» — когда необходимо, чтобы любой способ выполнения обновления приводил бы к выполнению условия.

Имеется большое количество результатов о различных семантиках логических программ, которые допускают отрицания в условиях предложений (нормальные логические программы) (см., например, [8]). Семантика совершенных моделей была предложена в [55] и основана на форме записи предложений. Известно [55, 56], что нормальная логическая программа может иметь не более одной совершенной модели. В [9] показано, что для стратифицированных логических программ совершенная модель всегда существует и является единственной стабильной моделью (о стабильных моделях см. [50] и более подробно [51]). В [29] установлено, что для дизъюнктивных логических программ определение существования совершенной модели является Е^-полной, а выводимости — nf-полной проблемой. В этой же работе установлены приблизительные границы сложности этих проблем для недизъюнктивных программ, а точная оценка их сложности сформулирована в качестве одной из открытых проблем.

Теория алгоритмической сложности была создана в работах Колмогорова, Соломонова, Чейтина и их учеников. Основы этой теории и ее современное состояние изложены в [1] и [46]. Работа [21] посвящена исследованию алгоритмической сложности рекурсивных множеств при ограничении на время вычисления. [15, 39] представляют собой обзоры результатов по структурной теории сложности. Наиболее значимые современные результаты из этой области собраны также в [40]. В работе [38] доказано, что если Р ф NP, то не существует редких Ш-трудных в NP множеств. В [2] показано, что при Р ф NP также не существует трудных по Тьюрингу для NP множеств, имеющих очень низкую алгоритмическую сложность: меньше к lg lg lg п для начального отрезка множества длины п. В качестве открытого в этой работе поставлен вопрос о том, можно ли усилить данный результат, повысив алгоритмическую сложность, при которой множества не могут быть NP-трудными. Основная теорема работы [14] говорит о том, что множества, к которым Ш-сводятся не сводящиеся к редким множества из ESPACE можно «слегка сжать», то есть сложность А^ в бесконечном числе точек меньше чем п — 2 lg п.

Цели работы

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

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

3. Установить сложность задачи построения совершенных моделей нормальных пропозициональных логических программ и задачи выводимости в совершенных моделях.

4. Выяснить возможность усиления результатов из [2, 14], связанных с алгоритмической сложностью и плотностью NP и ЕХР-трудных множеств.

Апробация работы

Первая часть работы докладывалась на международной конференции по математическим основаниям информатики LFCS'97 [27], вторая — на международной конференции по логическому программированию и немонотонному выводу LPNMR'99 [22]. Содержание главы 4 о совершенных моделях логических программ было опубликовано в журнале «Fundamenta Informa-ticae» [26]. Содержание последней части настоящего исследования было опубликовано в виде тезисов на конференции «Мальцевские чтения», посвященной 90-летию со дня рождения А.И.Мальцева [25].

Результаты, изложенные в настоящей диссертации неоднократно докладывались на семинаре по компьютерной логике ТвГУ. Содержание диссертации было представлено на семинаре МГУ по математической логике.

Структура диссертации

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

В главе 1 приводятся основные определения, которые используются в диссертации. Параграф 1.1 посвящен определениям, касающимся сложности вычислений, сводимостям, трудным и полным задачам, а в параграфе 1.2 мы напоминаем основные понятия, относящиеся к логическим программам.

Глава 2 посвящена исследованию сложности задачи выводимости в хор-новском фрагменте линейной логики для различных классов последовательностей хорновских импликаций и сложности распознавания принадлежности последовательностей хорновских импликаций к этим классам. В параграфе 2.2 мы исследуем классы перестановочных и параллельных последовательностей хорновских импликаций, введенных в [11], а также сильно параллельных последовательностей. Мы устанавливаем, что сложность распознавания параллельности зависит от того, ограничен ли размер алфавита заранее или нет. В параграфе 2.3 мы вводим понятие к-максимальной параллельности для каждого к = 1,2,. и максимальной параллельности, а также классы fc-максимально параллельных и максимально параллельных последовательностей хорновских импликаций. Мы устанавливаем, что классы ^-максимально параллельных последовательностей образуют иерархию по к, которая лежит между классами сильно параллельных и параллельных последовательностей. Сложности задач для класса ^-максимально параллельных последовательностей оказываются такими же, как и для классов перестановочных и сильно параллельных последовательностей хорновских импликаций. Сложность задач для класса максимально параллельных последовательностей хорновских импликаций зависит от ограниченности размера алфавита: при фиксированном размере алфавита сложность задач эквивалентна сложности задач для классов перестановочных, сильно параллельных и ^-максимально параллельных последовательностей, а если размер алфавита может быть произвольным, то сложность оказывается такой же, как и для класса параллельных последовательностей при нефиксированном алфавите.

В главе 3 мы рассматриваем сложность задачи обновления моделей логических программ. В параграфе 3.2 мы даем основные определения, связанные с данной задачей, формулируем понятие «минимального обновления». В 3.3 мы рассматриваем сложность задачи обновления, когда сигнатура зафиксирована. Данный параграф разбит на пять частей. Подпара-графы 3.3.1 и 3.3.2 носят вспомогательный характер: в первом из них мы приводим конструкцию, позволяющую доказывать нижнюю оценку сложности в случае, когда логическая программа содержит переменные, во втором — предлагаем способ построения минимально отклоняющейся модели, когда логическая программа является хорновской. Остальные три подпа-раграфа посвящены непосредственно исследованию сложности задачи обновления: в 3.3.3 рассматривается случай хорновских логических программ и положительных обновлений (вставок), в 3.3.4 — хорновских программ и произвольных обновлений, а в подпараграфе 3.3.5 — случай логических программ с отрицаниями (как следует из доказательства, вид обновления в этом случае не играет роли). Параграф 3.4 посвящен исследованию сложности задачи обновления моделей логических программ при нефиксированной сигнатуре. Мы показываем, что сложность этой задачи также зависит от того, является логическая программа хорновской или нет.

В главе 4 мы занимаемся исследованием сложности совершенных моделей нормальных пропозициональных логических программ. В параграфе 4.2 даны основные определения, а также некоторые технические понятия, используемые в доказательствах. Параграф 4.3 посвящен исследованию структуры совершенных моделей логических программ, основной результат которого — это алгоритм построения совершенной модели логической программы за полиномиальное время с NP-полным оракулом, то есть доказательство принадлежности задачи классу сложности Af. В параграфе 4.4 мы изучаем нижние оценки сложности задач совместности и выводимости в семантике совершенных моделей. Для этого мы вводим новый класс вычислительных устройств — разновидность машин Тьюринга с оракулом — и связанный с ним класс сложности — D2. Мы доказываем, что сложности задач совместности и следования в семантике совершенных моделей являются Вг-полными и соОг-полными соответственно.

5 глава посвящена исследованию алгоритмической сложности начальных отрезков NP-трудных и ЕХР-трудных проблем. Определения, связанные с алгоритмической сложностью, приводятся в 5.1.2. Параграф 5.2 посвящен исследованию нижней границы алгоритмической сложности NP-трудных по Тьюрингу множеств. Мы устанавливаем, что такие множества не могут иметь сложность к lg lg п (или меньше) начальных отрезков длины п почти для всех п. Параграф 5.3 посвящен исследованию множеств с высокой алгоритмической сложностью, «случайных» множеств. Мы устанавливаем, что хотя эти множества содержат максимально возможное количество информации, с практической точки зрения она мало полезна — любое множество из ЕХР П ESPACE, которое можно свести к «случайному», можно свести и к редкому.

В заключении приводятся основные результаты исследования.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Дудаков, Сергей Михайлович

Заключение

В работе решены следующие задачи:

1. (а) Определена сложность задач распознавания и применимости для классов перестановочных, параллельных и сильно параллельных последовательностей хорновских импликаций.

Ь) Предложены понятия ^-максимальной параллельности и максимальной параллельности. Для классов ^-максимально параллельных и максимально параллельных последовательностей хорновских импликаций установлена сложность задач распознавания и применимости.

Оценки сложности задач, которые получены в настоящей работе и статье [11] (см. сноски), приведены в таблице 6.1.

Список литературы диссертационного исследования кандидат физико-математических наук Дудаков, Сергей Михайлович, 2000 год

1. Агафонов В.Н. Сложность алгоритмов и вычислений. Часть 2. — Новосибирск, изд-во НГУ, 1975.

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

3. Мучник А.А. Добавление переводчика к статьям «Об альтернировании, I, II». // Кибернетический сборник, вып. 20. — Москва, Мир, 1983, сс. 141-158.

4. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. — Москва, Мир, 1972.

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

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

7. Abiteboul S. Updates a new Frontier: Proc. of the Second International Conference on the Theory of Databases, ICDT'88. LNCS 326 - 1988 -pp. 1-18.

8. Apt K. Logic programming, chapter 10 in van Leeuwen ed. Handbook of Theoretical Computer Science, Elsevier Science — 1990.

9. Apt K., Blair H., Walker A. Towards a theory of declarative knowledge. // Foundations of Deductive Databases and Logic Programming — 1988 — pp. 99-148.

10. Archangelsky D.A., Taitslin M.A. Linear Logic With Fixed Resources. // Annals of Pure and Applied Logic, v. 67 — 1994 — pp. 3-28.

11. Arvind V., Han Y., Hemachandra L., Kobler J., Lozano A., Mundhenk M., Ogiwara M., Schoning U., Silvestri R., Thierauf T. Reduction to sets of low information content, j j Complexity theory. — Cambridge, Cambridge University Press, 1993 — pp. 1-46.

12. Baral C., Lobo J. Formal Characterization of Active Databases: Logic in Databases. Intern. Workshop LID'96. Proceedings. — San Milano, Italy. — 1996 pp. 175-195.

13. Book R. V., Lutz J. H. On languages with very high information content: 7th Structural complexity theory — 1992 — pp. 255-259.

14. Buhrman H., Torenvliet L. On the structure of complete sets: 9th Structural complexity theory — 1994 — pp. 118-133.

15. Chandra A.K., Kozen D.C., Stockmeyer L.J. Alternation. // J. Ass. Comput. Mach., v.28, № 1 1981 - pp. 114-133.

16. Complexity Theory. Retrospective II. / Editors: Hemaspaandra L.A., Selman A.L. — New-York, Springer-Verlag, 1997.

17. Cook S.A. The complexity of theorem proving procedures: Proceeding of the 3rd Annual ACM Symposium on theory of computing — 1971 — pp. 151-158.

18. Dantsin E., Eiter Т., Gottlob G., Voronkov A. Complexity and Expressive Power of Logic Programming: Proc. 12th Annual IEEE Conference on Computational Complexity (CCC'97) Ulm, 1997 - pp. 1-20.

19. Dayal U., Hanson E., and Widom J. Active database systems. I j Modern Database Systems. — Addison Wesley, 1995 — pp. 436-456

20. Dekhtyar' M.I. Complexity spectra of recursive sets and approximability of initial segments of complete problems. // Elektronische Informations-verarbeitung Kybernetik, 15 — 1979 — pp. 11-32.

21. Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Monotone Expansion of Updates in Logical Databases: Proc. of 5th International Conference LPNMR'99 Berlin, Springer-Verlag, 1999 - pp. 132-146.

22. Dekhtyar M., Dikovsky A., Spyratos N. On Conservative Enforced Updates: Proceedings of 4th International Conference, LPNMR'97. Dagstuhl Castle, Germany, LNCS 1265 1997 - pp. 244-257.

23. Dekhtyar M., Dikovsky A., Spyratos N. On Logically Justified Updates: Proc. of the 1998 Joint International Conference and Symposium on Logic Programming. MIT Press 1998 - pp. 250-264.

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

25. Dudakov S.M. On the complexity of perfect models of logic programs. // Fundamenta Informaticae. vol. 39(3) - 1999 — pp. 249-258.

26. Dudakov S.M. The Concurrency Complexity for the Horn Fragment of Linear Logic: Proc of the fourth Intern. Simp. LFCS'97. — Springer, 1997 pp. 78-87.

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

28. Eiter Т., Gottlob G. On the computational cost of disjunctive logic programming: Propositional case // AMAI, 15 — 1995 — pp. 289-323.

29. Eiter Т., Gottlob G. Propositional circumscription and extended closed world reasoning are Ilf -complete: Theoretical Computer Science, 114(2) — 1993 pp 231-245.

30. Fischer M., Rabin M. Super exponential complexity of Presburger's arithmetic: SIAM AMS Proc., 7 1974 - pp.27-41.

31. Fu B. With quasi-linear queries, EXP is not polynomial time Turing reducible to sparse sets: Proc. Structure in Complexity Theory 8th annual conference — San Diego, IEEE computer society press, 1993 — pp.185-193.

32. Garey M.R., Johnson D.S. Computers and Intractability. A Guide to the Theory of NP-Completeness. — San Francisco, W.H.Freeman and Company, 1979.

33. Gelfond M., Lifschitz V. The stable model semantics for logic programming: Proc. 5th International Conf. and Symp. on Logic Programming. — The MIT Press, 1988 pp. 1070-1080.

34. Girard J.Y. Linear Logic: Theoretical Computer Science, v. 50 — 1987 — pp. 1-102.

35. Grant J., Minker J. Integrity constraints in knowledge based systems, j j Knowledge engineering, vol 1 and 2. — Mcgraw-Hill Publishers, 1990 — pp. 1-25.

36. Halfeld Ferrari Alves M., Laurent D., Spyratos N., Stamate D. Update rules and revision programs. / Rapport de Recherche Universit£ de Paris-Sud, Centre d'Orsay, LRI 1010 № 12 1995.

37. Homer S., Longpre L. On reductions of NP sets to sparse sets: 6th Structural complexity theory — 1991 — pp. 79-88.

38. Hemachandra L. A., Ogiwara M. How hard are sparse sets: 7th Structural complexity theory 1992 - pp. 222-238.

39. Complexity theory. Retrospective II. / Ed. Hemachandra L. A., Selman A. L. — New York, Springer-Verlag, 1997.

40. Kanovich M.I. Horn Programming in Linear Logic is NP-complete: Proc.7-th Annual IEEE Symposium on Logic in Computer Science — 1992 pp. 200-210.

41. Kadin J. pNplosn] and sparse Turing complete sets of NP. // Journal of Computer and System Sciences, 39(3) 1989 - pp. 282-298.

42. Karp R.M. Reducibility among combinatorial problems. // Complexity of Computer Computations. — New-York, Plenum Press — 1972 — pp. 82104.

43. Karp R., Lipton R. Some connections between nonuniform and uniform complexity classes: Proc. of the 12th ACM Symp. of Theory of Computing 1980 - pp.302-309.

44. Ladner R., Lynch N., Selman A. Comparison of polynomial-time reduc-ibilities. // Theoretical Computer Science, № 1 — 1975 — pp. 103-123.

45. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and it's Application. — Springer — 1998.

46. Lincoln P., Mitchell J., Scerdov A., and Shankar N. Decision Problems for Propositional Linear Logic: Proc.31-th IEEE Symposium on Foundation of Computer Science — 1990 — pp. 662-671.

47. Lloyd J.W. Foundations of Logic Programming. Second, Extended Edition. — Springer-Verlag, 1993.

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

49. Marek W., Truszczynski M. Autoepistemic logic. // Journal of ACM, 38, 3 1991 - pp. 588-619.

50. Marek W., Truszczynski M. Nonmonotonic logics; context-dependent reasoning. Springer-Verlag — 1993.139

51. Meyer A.R., Stockmeyer L.J. The equivalence problem for regular expressions with squaring requires exponential time: Proc.l3th Ann. Symp. on Switching and Automata Theory — 1972 — pp. 125-129.

52. Ogiwara M., Watanabe O. On Polynomial-time bounded truth-table reduc-ibility of NP sets to sparse sets. // SIAM Journal on Computing, 20(3) — 1991 pp.471-483.

53. Picouet Ph., Vianu V. Expressiveness and Complexity of Active Databases: 6th Int. Conf. on Database Theory, ICDT'97. LNCS 1186 1997 - pp. 155-172

54. Przymusinski T. On semantics of stratified deductive databases. // Foundations of Deductive Databases and Logic Programming — 1988 — pp. 433-443.

55. Przymusinski T. Perfect model semantics: Proc. Intern. Conf. on Logic Programming 1988 - pp. 1081-1096.

56. Stockmeyer L.J. The polynomial time hierarchy: Theoretical Computer Science, v. 3, № 1 1977 - pp. 1-22.

57. Ukkonen E. Two results on polynomial time truth-table reductions to sparse sets // SIAM J. Comput. Vol. 12, No. 3 1983 - pp. 580-587.