اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدZero-one laws for existential first order sentences of bounded quantifier depth
61
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For any fixed positive integer $k$, let $alpha_{k}$ denote the smallest $alpha in (0,1)$ such that the random graph sequence $left{Gleft(n, n^{-alpha}right)right}$ does not satisfy the zero-one law for the set $mathcal{E}_{k}$ of all existential first order sentences that are of quantifier depth at most $k$. This paper finds upper and lower bounds on $alpha_{k}$, showing that as $k rightarrow infty$, we have $alpha_{k} = left(k - 2 - t(k)right)^{-1}$ for some function $t(k) = Theta(k^{-2})$. We also establish the precise value of $alpha_{k}$ when $k = 4$.
قيم البحث
اقرأ أيضاً
We prove game-theoretic generalizations of some well known zero-one laws. Our proofs make the martingales behind the laws explicit, and our results illustrate how martingale arguments can have implications going beyond measure-theoretic probability.
Classical scope-assignment strategies for multi-quantifier sentences involve quantifier phrase (QP)-movement. More recent continuation-based approaches provide a compelling alternative, for they interpret QPs in situ - without resorting to Logical Fo
rms or any structures beyond the overt syntax. The continuation-based strategies can be divided into two groups: those that locate the source of scope-ambiguity in the rules of semantic composition and those that attribute it to the lexical entries for the quantifier words. In this paper, we focus on the former operation-based approaches and the nature of the semantic operations involved. More specifically, we discuss three such possible operation-based strategies for multi-quantifier sentences, together with their relative merits and costs.
We study the critical probability for the metastable phase transition of the two-dimensional anisotropic bootstrap percolation model with $(1,2)$-neighbourhood and threshold $r = 3$. The first order asymptotics for the critical probability were recen
tly determined by the first and second authors. Here we determine the following sharp second and third order asymptotics: [ p_cbig( [L]^2,mathcal{N}_{(1,2)},3 big) ; = ; frac{(log log L)^2}{12log L} , - , frac{log log L , log log log L}{ 3log L} + frac{left(log frac{9}{2} + 1 pm o(1) right)log log L}{6log L}. ] We note that the second and third order terms are so large that the first order asymptotics fail to approximate $p_c$ even for lattices of size well beyond $10^{10^{1000}}$.
In this paper we study first-passge percolation models on Delaunay triangulations. We show a sufficient condition to ensure that the asymptotic value of the rescaled first-passage time, called the time constant, is strictly positive and derive some u
pper bounds for fluctuations. Our proofs are based on renormalization ideas and on the method of bounded increments.
Markov categories are a recent category-theoretic approach to the foundations of probability and statistics. Here we develop this approach further by treating infinite products and the Kolmogorov extension theorem. This is relevant for all aspects of
probability theory in which infinitely many random variables appear at a time. These infinite tensor products $bigotimes_{i in J} X_i$ come in t
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
