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

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

В настоящей работе мы привели примеры экзистенциальпых монадических формул, вероятность истинности которых не имеет предела на биномиальном случайном разреженном графе G(n, n–α). При α <  соответствующие примеры содержат всего одну монадическую переменную.

Об авторах

А. Н. Егорова

Московский физико-технический институт (национальный исследовательский университет)

Автор, ответственный за переписку.
Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9

М. Е. Жуковский

Московский физико-технический институт (национальный исследовательский университет)

Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9

Список литературы

  1. Жуковский M.E., Райгородский А.М. // УМН. 2015. Т. 70. № 1. С. 35–88.
  2. Spencer J.H. The Strange Logic of Random Graphs. B.: Springer Verlag, 2001.
  3. Верещагин Н.К., Шень А. Языки и исчисления. М.: МНЦМО, 2000.
  4. Жуковский М.Е., Санчез М.Г. // ДАН. 2017. Т. 477. № 5. С. 513–515.
  5. Le Bars J.-M. // Inform. Processing Lett. 2001. V. 77. P. 43–48.
  6. Janson S., Luczak T., Rucinski A. Random Graphs. N.Y.: Wiley, 2000.
  7. Глебский Ю.В., Коган Д.И., Легонький М.И., Таланов В.А. // Кибернетика. 1969. Т. 2. С. 17–27.
  8. Fagin R. // J. Symbolic Logic. 1976. V. 41. P. 50–58.
  9. Жуковский М.Е., Медведева А.Е. // Мат. заметки. 2016. Т. 99. № 3. С. 342–349.
  10. Жуковский М.Е., Островский Л.Б. // Изв. РАН. Сер. мат. 2017. Т. 81. № 6. С. 100–113.
  11. Matushkin A.D., Zhukoυskii M.E. // Discrete Appl. Math. 2018. V. 236. P. 329–346.
  12. Kaufmann M., Shelah S. // Discrete Math. 1985. V. 54. P. 285–293.
  13. Kaufmann M. Counterexample to the 0-1 Law for Existential Monadic Second-Order Logic. Technical Report. CLI Internal Note 32. Computational Logic. December 1987.
  14. Shelah S., Spencer J.H. // J. Amer. Math. Soc. 1988. V. 1. P. 97–115.
  15. Tyszkiewicz J. // Lect. Notes in Comput. Sci. 1993. V. 702. P. 425–439.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2019