Научная тема: «СЕМАНТИКА И АНАЛИЗ СЛОЖНОСТИ АЛГОРИТМИЧЕСКИХ ПРОБЛЕМ ДИНАМИЧЕСКИХ СИСТЕМ И ЯЗЫКОВ, ИСПОЛЬЗУЮЩИХ ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ»
Специальность: 05.13.17
Год: 2009
Основные научные положения, сформулированные автором на основании проведенных исследований:
  1. Установлены оценки сложности задач, связанных с проблемой наи­меньших достаточных изменений (НДИ) при выполнения обновле­ний БД и предложены эвристические алгоритмы для решения про­блемы НДИ для статических и динамических ограничений целост­ности и алгоритмы для максимального расширения обновлений и упрощения ограничений целостности.
  2. Определена формальная модель взаимодействия интеллектуально­го агента - динамической дедуктивной базы данных - с внешней средой и установлена сложность верификации свойств устойчиво­го поведения (перспективности, стабильности и гомеостатичности) для различных классов таких систем, определяемых типом логи­ческой программы с обновлениями в качестве интеллектуальной компоненты системы и типом условия, выделяющего допустимые состояния.
  3. Определены формальные модели детерминированных, недетерми­нированных и вероятностных мультиагентных (МА-) систем, бази­рующиеся на архитектуре IMPACT, и получены оценки сложно­сти верификации свойств поведения МА-систем, выразимых сред­ствами временных логик, для различных классов МА-систем, раз­личающихся типами используемых в качестве интеллектуальной компоненты агентов логических программ, количеством агентов в системе, количеством различных видов сообщений и количеством параметров в описаниях состояний.
  4. Ранее определенный класс логических (р-) программ с интерваль­ными вероятностями расширен до класса дизъюнктивных логи­ческих (dp-) программ. Для обоих классов изучено соотношение между теоретико-модельной семантикой "возможных миров" и се­мантикой минимальной неподвижной точки. Доказана NP-полнота проблемы совместности (существования модели) и и проблемы сле­дования дляр- и dp-программ. Получено явное описание множества моделей, задаваемых р и dp-программами Построены алгоритмы для вычисления теоретико-модельной семантикир и dp-программ, использующие специальные эвристики для сокращения перебора.
  5. Определен класс рекурсивных программ, для которых семантика вызова "по значению" совпадает с семантикой минимальной непо­движной точки и показано, что Рефал-программы входят в этот класс. Доказано, что задача синтаксического отождествления, ре­шаемая на каждом шаге работы Рефал-машины является NP-полной и получены верхние оценки сложности этой задачи.
  6. Исследована сложность аппроксимации трудных проблем более про­стыми на начальных отрезках входных данных. В частности, полу­чены оценки сложности аппроксимации проблем, которые полны или трудны для различных детерминированных и недетерминиро­ванных сложноегных классов и установлена связь между верхними и нижними оценками сложности вычисления проблемы и сложно­стью ее аппроксимации.
Список опубликованных работ
[1] Дехтярь М.И. О сложности аппроксимации рекурсивных множеств //Electronische Informatik unci 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. 11-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. 0.42 52.

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

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

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

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

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

[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. (лич-ный вклад 70.)

[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. (личный вклад 70.)

[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.

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

[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. PSF99, 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. (личный вклад 40.)

[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. L, Dikovsky A. Ja., Valiev M. K. Complexity of Multi-Agent 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. (личный вклад 40.)

[34] 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. (личный вклад 2C.)

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

[36] Валиев М.К., Дехтярь М.И., Диковский А.Я. О сложности ве-рификации систем взаимодействующих интеллектуальных агентов // Труды международных конференций "Интеллектуальные систе¬мы" (IEEEE AIS03) и "Интеллектуальный САПР"( CAD2003), Див-номорское, 2-8 сентября 2003, М.: Физматлит, 2003, С. 475-481. (лич¬ный вклад 20.)

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

[38] 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. (личный вклад 40.)

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

[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., Дехтярь М.И., Диковский А.Я. О свойствах много-агентных систем с вероятностными каналами связи // Труды I V-ofi Межд. научно-практической конференции "Интегрированные моде-ли и мягкие вычисления в искусственном интеллекте", М.: Физмат-лит, Коломна, 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. (личный вклад 40.)

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

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

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