|
Problemy Peredachi Informatsii, 2017, Volume 53, Issue 4, Pages 95–108
(Mi ppi2255)
|
|
|
|
Large Systems
Quantifier alternation in first-order formulas with infinite spectra
M. E. Zhukovskii Derzhavin Tambov State University, Tambov, Russia
Abstract:
The spectrum of a first-order formula is the set of numbers $\alpha$ such that for a random graph in a binomial model where the edge probability is a power function of the number of graph vertices with exponent $-\alpha$ the truth probability of this formula does not tend to either zero or one. In 1990 J. Spenser proved that there exists a first-order formula with an infinite spectrum. We have proved that the minimum quantifier depth of a first-order formula with an infinite spectrum is either 4 or 5. In the present paper we find a wide class of first-order formulas of depth 4 with finite spectra and also prove that the minimum quantifier alternation number for a first-order formula with an infinite spectrum is 3.
Received: 20.01.2017 Revised: 15.04.2017
Citation:
M. E. Zhukovskii, “Quantifier alternation in first-order formulas with infinite spectra”, Probl. Peredachi Inf., 53:4 (2017), 95–108; Problems Inform. Transmission, 53:4 (2017), 391–403
Linking options:
https://www.mathnet.ru/eng/ppi2255 https://www.mathnet.ru/eng/ppi/v53/i4/p95
|
Statistics & downloads: |
Abstract page: | 191 | Full-text PDF : | 24 | References: | 21 | First page: | 10 |
|