Email this article Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations
- Authors: Zhukovskii M.E.1, Matushkin A.D.2
-
Affiliations:
- Tambov State University
- Moscow Institute of Physics and Technology (State University)
- Issue: Vol 96, No 1 (2017)
- Pages: 326-328
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225189
- DOI: https://doi.org/10.1134/S1064562417040093
- ID: 225189
Cite item
Open Access
Access granted
Subscription Access
Abstract
Spectra of first-order formulas are studied. The spectrum of a first-order formula is the set of all positive α such that either this formula is true for the random graph G(n, n−α) with an asymptotic probability being neither 0 nor 1 or the limit does not exist. It is well known that there exists a first-order formula with an infinite spectrum. The minimum number of quantifier alternations in such a formula is found.
About the authors
M. E. Zhukovskii
Tambov State University
Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, Tambov
A. D. Matushkin
Moscow Institute of Physics and Technology (State University)
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700
