Spectrum of FO logic with quantifier depth 4 is finite

DOI10.1145/3641547MaRDI QIDQ6493420zbMATH OpenWikidataFDO

Authors Yury Yarovikov, M. E. Zhukovskii

Publication date 26 April 2024

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

Full work available at URL https://doi.org/10.1145/3641547

zbMATH Keywords

first-order logicrandom graphsspectra of first order sentenceszero-one law

Mathematics Subject Classification ID

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

Cites work

• An application of games to the completeness problem for formalized theories
• Bounded quantifier depth spectra for random graphs
• Elements of finite model theory.
• Finite model theory and its applications.
• First order sentences about random graphs: small number of alternations
• scientific article; zbMATH DE number 4041966 (Why is no real title available?)
• Infinite spectra in the first order theory of graphs
• Monadic second-order properties of very sparse random graphs
• On infinite spectra of first-order properties of random graphs
• On limit points of spectra of first-order sentences with quantifier depth 4
• On the first-order complexity of induced subgraph isomorphism
• On the zero-one 4-law for the Erdős-Rényi random graphs
• Probabilities on finite models
• Random graphs: models and asymptotic characteristics
• The largest critical point in the zero-one k-law
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strange logic of random graphs
• Threshold functions
• Threshold spectra via the Ehrenfeucht game
• Universal zero-one k-law
• Zero-one \(k\)-law
• Zero-One Laws for Sparse Random Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6493420)