اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQuantifier alternation in a class of recursively defined tree properties
63
0
0.0
(
0
)
تأليف
Moumanti Podder
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Alternating quantifier depth is a natural measure of difficulty required to express first order logical sentences. We define a sequence of first order properties on rooted, locally finite trees in a recursive manner, and provide rigorous arguments for finding the alternating quantifier depth of each property in the sequence, using Ehrenfeucht-Fra{i}ss{e} games.
قيم البحث
اقرأ أيضاً
The only C*-algebras that admit elimination of quantifiers in continuous logic are $mathbb{C}, mathbb{C}^2$, $C($Cantor space$)$ and $M_2(mathbb{C})$. We also prove that the theory of C*-algebras does not have model companion and show that the theory
of $M_n(mathcal {O_{n+1}})$ is not $forallexists$-axiomatizable for any $ngeq 2$.
Given two structures $G$ and $H$ distinguishable in $fo k$ (first-order logic with $k$ variables), let $A^k(G,H)$ denote the minimum alternation depth of a $fo k$ formula distinguishing $G$ from $H$. Let $A^k(n)$ be the maximum value of $A^k(G,H)$ ov
er $n$-element structures. We prove the strictness of the quantifier alternation hierarchy of $fo 2$ in a strong quantitative form, namely $A^2(n)ge n/8-2$, which is tight up to a constant factor. For each $kge2$, it holds that $A^k(n)>log_{k+1}n-2$ even over colored trees, which is also tight up to a constant factor if $kge3$. For $kge 3$ the last lower bound holds also over uncolored trees, while the alternation hierarchy of $fo 2$ collapses even over all uncolored graphs. We also show examples of colored graphs $G$ and $H$ on $n$ vertices that can be distinguished in $fo 2$ much more succinctly if the alternation number is increased just by one: while in $Sigma_{i}$ it is possible to distinguish $G$ from $H$ with bounded quantifier depth, in $Pi_{i}$ this requires quantifier depth $Omega(n^2)$. The quadratic lower bound is best possible here because, if $G$ and $H$ can be distinguished in $fo k$ with $i$ quantifier alternations, this can be done with quantifier depth $n^{2k-2}$.
We give a valuation theoretic characterization for a real closed field to be recursively saturated. Our result extends the characterization of Harnik and Ressayre cite{hr} for a divisible ordered abelian group to be recursively saturated.
The server-centric data centre network architecture can accommodate a wide variety of network topologies. Newly proposed topologies in this arena often require several rounds of analysis and experimentation in order that they might achieve their full
potential as data centre networks. We propose a family of novel routing algorithms on two well-known data centre networks of this type, (Generalized) DCell and FiConn, using techniques that can be applied more generally to the class of networks we call completely connected recursively-defined networks. In doing so, we develop a classification of all possible routes from server-node to server-node on these networks, called general routes of order $t$, and find that for certain topologies of interest, our routing algorithms efficiently produce paths that are up to 16% shorter than the best previously known algorithms, and are comparable to shortest paths. In addition to finding shorter paths, we show evidence that our algorithms also have good load-balancing properties.
Work of Eagle, Farah, Goldbring, Kirchberg, and Vignati shows that the only separable C*-algebras that admit quantifier elimination in continuous logic are $mathbb{C},$ $mathbb{C}^2,$ $M_2(mathbb{C}),$ and the continuous functions on the Cantor set.
We show that, among finite dimensional C*-algebras, quantifier elimination does hold if the language is expanded to include two new predicate symbols: One for minimal projections, and one for pairs of unitarily conjugate projections. Both of these predicates are definable, but not quantifier-free definable, in the usual language of C*-algebras. We also show that adding just the predicate for minimal projections is sufficient in the case of full matrix algebras, but that in general both new predicate symbols are required.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
