Отправить статью по E-mail Опровержение закона нуля или единицы для экзистенциальных монадических свойств разреженного биномиального случайного графа
- Авторы: Егорова А.Н.1, Жуковский М.Е.1
-
Учреждения:
- Московский физико-технический институт (национальный исследовательский университет)
- Выпуск: Том 484, № 5 (2019)
- Страницы: 519-522
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/12758
- DOI: https://doi.org/10.31857/S0869-56524845519-522
- ID: 12758
Цитировать
Полный текст
Аннотация
В настоящей работе мы привели примеры экзистенциальпых монадических формул, вероятность истинности которых не имеет предела на биномиальном случайном разреженном графе G(n, n–α). При α < соответствующие примеры содержат всего одну монадическую переменную.
Об авторах
А. Н. Егорова
Московский физико-технический институт (национальный исследовательский университет)
Автор, ответственный за переписку.
Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9
М. Е. Жуковский
Московский физико-технический институт (национальный исследовательский университет)
Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9
Список литературы
- Жуковский M.E., Райгородский А.М. // УМН. 2015. Т. 70. № 1. С. 35–88.
- Spencer J.H. The Strange Logic of Random Graphs. B.: Springer Verlag, 2001.
- Верещагин Н.К., Шень А. Языки и исчисления. М.: МНЦМО, 2000.
- Жуковский М.Е., Санчез М.Г. // ДАН. 2017. Т. 477. № 5. С. 513–515.
- Le Bars J.-M. // Inform. Processing Lett. 2001. V. 77. P. 43–48.
- Janson S., Luczak T., Rucinski A. Random Graphs. N.Y.: Wiley, 2000.
- Глебский Ю.В., Коган Д.И., Легонький М.И., Таланов В.А. // Кибернетика. 1969. Т. 2. С. 17–27.
- Fagin R. // J. Symbolic Logic. 1976. V. 41. P. 50–58.
- Жуковский М.Е., Медведева А.Е. // Мат. заметки. 2016. Т. 99. № 3. С. 342–349.
- Жуковский М.Е., Островский Л.Б. // Изв. РАН. Сер. мат. 2017. Т. 81. № 6. С. 100–113.
- Matushkin A.D., Zhukoυskii M.E. // Discrete Appl. Math. 2018. V. 236. P. 329–346.
- Kaufmann M., Shelah S. // Discrete Math. 1985. V. 54. P. 285–293.
- Kaufmann M. Counterexample to the 0-1 Law for Existential Monadic Second-Order Logic. Technical Report. CLI Internal Note 32. Computational Logic. December 1987.
- Shelah S., Spencer J.H. // J. Amer. Math. Soc. 1988. V. 1. P. 97–115.
- Tyszkiewicz J. // Lect. Notes in Comput. Sci. 1993. V. 702. P. 425–439.
Дополнительные файлы
