Отправить статью по E-mail Законы нуля или единицы для формул с k переменными
- Авторы: Жуковский М.Е.1, Разафимахатратра А.С.2
-
Учреждения:
- Московский физико-технический институт (национальный исследовательский университет)
- Реджайнский университет или Университет Реджайны
- Выпуск: Том 486, № 2 (2019)
- Страницы: 156-158
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/13404
- DOI: https://doi.org/10.31857/S0869-56524862156-158
- ID: 13404
Цитировать
Полный текст
Аннотация
Мы рассматриваем фрагмент логики первого порядка на графах, состоящий из предложений с k переменными. Мы утверждаем, что при случайный граф G(n, n-α) подчиняется закону нуля или единицы для этого фрагмента. Более того, для каждого ε > 0 найдётся , при котором случайный граф G(n, n-α) не подчиняется этому закону.
Об авторах
М. Е. Жуковский
Московский физико-технический институт (национальный исследовательский университет)
Автор, ответственный за переписку.
Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9
А. С. Разафимахатратра
Реджайнский университет или Университет Реджайны
Email: andriahermanana@aims.edu.gh
Канада, SK S4S 0A2, Реджайна, Васкана-Паркуэй 3737
Список литературы
- Libkin L. Elements of finite model theory. Texts in Theoretical Computer Science. An EATCS Series B.: SpringerVerlag, 2004.
- Zhukovskii M.E., Raigorodskii A.M. // Rus. Math. Surv. 2015. V. 70. № 1. P. 33-81.
- Burkin A.V., Zhukovskii M.E. In: Mathematics. 2018. V. 209. № 2. P. 163-186.
- Zhukovskii M.E., Ostrovskii L.B. // Izv. Math. 2017. V. 81. № 6. P. 1155-1167.
- Жуковский М.Е., Санчез М.Г. // ДАН. 2017. Т. 477. № 5. С. 513-515.
- Spencer J.H., Zhukovskii M.E. // Discrete Math. 2016. V. 339. № 6. P. 1651-1664.
- Fagin R. // J. Symbolic Logic. 1976. V. 41. P. 50-58.
- Glebskii Y.V., Kogan D.I., Liogon’kii M.I., Talanov V.A. // Cybernetics. 1969. V. 5. P. 142-154.
- Spencer J.H. // Discrete App. Math. 1991. V. 30. P. 235-252.
- Shelah S., Spencer J.H. // J. Amer. Math. Soc. 1988. V. 1. P. 97-115.
- Kolaitis P.G., Vardi M.Y. // Inform. and Comput. 1992. V. 98. P. 258-294.
- Lynch J.F. Proc. of the 8th IEEE Symp. on Logic in Computer Science. Cambridge, 1993. P. 191-198.
- McArthur M. // Logic and Random Structures. 1997. V. 33. P. 53-63.
- Spencer J.H. // Combinatorica. 1990. V. 10. № 1. P. 95-102.
- Zhukovskii M.E. // Moscow J. Combin. and Number Theory. 2016. V. 6. № 4. P. 73-102.
Дополнительные файлы
