Spectrum of FO logic with quantifier depth 4 is finite

DOI10.1145/3641547WikidataQ129631853 ScholiaQ129631853MaRDI QIDQ6493420

M. E. Zhukovskii, Yury Yarovikov

Publication date: 26 April 2024

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

zbMATH Keywords

first-order logicrandom graphszero-one lawspectra of first order sentences

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded quantifier depth spectra for random graphs
• Universal zero-one \(k\)-law
• Zero-one \(k\)-law
• Finite model theory and its applications.
• Elements of finite model theory.
• Threshold spectra via the Ehrenfeucht game
• Infinite spectra in the first order theory of graphs
• Threshold functions
• First order sentences about random graphs: small number of alternations
• On limit points of spectra of first-order sentences with quantifier depth 4
• On the zero-one 4-law for the Erdős-Rényi random graphs
• Monadic second-order properties of very sparse random graphs
• On infinite spectra of first-order properties of random graphs
• An application of games to the completeness problem for formalized theories
• Zero-One Laws for Sparse Random Graphs
• Probabilities on finite models
• Random graphs: models and asymptotic characteristics
• The largest critical point in the zero-one k-law
• The descriptive complexity of subgraph isomorphism without numerics
• The strange logic of random graphs

This page was built for publication: Spectrum of FO logic with quantifier depth 4 is finite