Некоторые эффективно разрешимые классы вычисления формул темпоральных и модальных логик

Автор: Алифанов Дмитрий Владимирович

Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu

Статья в выпуске: 12, 2009 года.

Бесплатный доступ

Представлены полиномиальные алгоритмы решения частных проблем выполнимости формул темпоральных и модальных логик с ограничением для Крипкеграфов. Использована игровая интерпретация выполнимости и результат Цермело о наличии равновесия в позиционных играх с полной информацией.

Короткий адрес: https://sciup.org/14968630

IDR: 14968630

Список литературы Некоторые эффективно разрешимые классы вычисления формул темпоральных и модальных логик

Ахо, А. Построение и анализ вычислительных алгоритмов/А. Ахо, Дж. Хопкрофт, Дж. Ульман. -М.: Мир, 1979. -С. 216-223.
Лебедев, В. Н. Поиск и структура стационарных равновесий в циклических играх/B. Н. Лебедев//Мат. заметки. -2000. -Т. 67. -№ 6. -С. 913-921.
Karzanov, A. V. Cyclical games with prohibitions/A. V. Karzanov, V. N. Lebedev//Mathematical Programming. -1993. -V. 60. -P. 277-293.
Emerson, E. A. On model-checking for fragments of µ-calculus./E. A. Emerson, C. S. Jutla, A. P. Sistla//Computer Aided Verification, Proc. 5lh Int. Workshop. -V. 697. -P. 385-396.
Elounda, Crete, June 1993. Lecture Notes in Computer Science, Springer-Verlag.
Zermelo, E. Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels/E. Zermelo//Proc. 5th Congr. Mathematicians. -Cambridge Univ. Press., 1912. -P. 501-504.
Лебедев, В. Н. Игровые аспекты верификации программ/В. Н. Лебедев, М. С. Черничкин//Известия РАН. Теория и системы управления. -2005. -№ 5. -C. 40-45.
Биркгоф, Г. Теория решеток/Г. Биркгоф. -М.: Наука, 1984. -568 с.
Захаров, В. А. Эффективные алгоритмы проверки выполнимости формул темпоральной логики CTL и их применение для верификации параллельных программ/В. А. Захаров, Д. В. Царьков//Программирование. -1998. -№ 4. -С. 3-18.
Захаров, В. А. Математическая логика и логическое программирование/В. А. Захаров. -Режим доступа: http://mathcyb.cs.msu.su/courses/logprog.html

Еще

Краткое сообщение