×
Podder, Moumanti; Zhukovskii, Maksim

Zero-one laws for existential first-order sentences of bounded quantifier depth. (English) Zbl 1505.03078

ACM Trans. Comput. Log. 23, No. 2, Article No. 12, 27 p. (2022).

MSC:

03C13 Model theory of finite structures
05C80 Random graphs (graph-theoretic aspects)
60F20 Zero-one laws

Keywords:

existential first-order logic; zero-one laws; Ehrenfeucht games; strictly balanced graphs; \( \alpha \)-safe pairs; graph extension properties
Cite Review PDF
Full Text: DOI arXiv