RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 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.

UDC: 621.391.1+519.1

Received: 20.01.2017
Revised: 15.04.2017


 English version:
Problems of Information Transmission, 2017, 53:4, 391–403

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025