Back to Search
Start Over
Spectrum of FO Logic with Quantifier Depth 4 is Finite.
- Source :
- ACM Transactions on Computational Logic; Apr2024, Vol. 25 Issue 2, p1-24, 24p
- Publication Year :
- 2024
-
Abstract
- The k-spectrum is the set of all α > 0 such that G(n,n<superscript>−α</superscript>) does not obey the 0-1 law for FO sentences with quantifier depth at most k. In this article, we prove that the minimum k such that the k-spectrum is infinite equals 5. [ABSTRACT FROM AUTHOR]
- Subjects :
- LOGIC
FIRST-order logic
RANDOM graphs
Subjects
Details
- Language :
- English
- ISSN :
- 15293785
- Volume :
- 25
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- ACM Transactions on Computational Logic
- Publication Type :
- Academic Journal
- Accession number :
- 176651817
- Full Text :
- https://doi.org/10.1145/3641547