Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSecond order logic on random rooted trees
120
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton-Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).
rate research
Read More
We consider a specific class of tree structures that can represent basic structures in linguistics and computer science such as XML documents, parse trees, and treebanks, namely, finite node-labeled sibling-ordered trees. We present axiomatizations of the monadic second-order logic (MSO), monadic transitive closure logic (FO(TC1)) and monadic least fixed-point logic (FO(LFP1)) theories of this class of structures. These logics can express important properties such as reachability. Using model-theoretic techniques, we show by a uniform argument that these axiomatizations are complete, i.e., each formula that is valid on all finite trees is provable using our axioms. As a backdrop to our positive results, on arbitrary structures, the logics that we study are known to be non-recursively axiomatizable.
The Maki-Thompson rumor model is defined by assuming that a population represented by a graph is subdivided into three classes of individuals; namely, ignorants, spreaders and stiflers. A spreader tells the rumor to any of its nearest ignorant neighbors at rate one. At the same rate, a spreader becomes a stifler after a contact with other nearest neighbor spreaders, or stiflers. In this work we study the model on random trees. As usual we define a critical parameter of the model as the critical value around which the rumor either becomes extinct almost-surely or survives with positive probability. We analyze the existence of phase-transition regarding the survival of the rumor, and we obtain estimates for the mean range of the rumor. The applicability of our results is illustrated with examples on random trees generated from some well-known discrete distributions.
Motivated by the problem of designing inference-friendly Bayesian nonparametric models in probabilistic programming languages, we introduce a general class of partially exchangeable random arrays which generalizes the notion of hierarchical exchangeability introduced in Austin and Panchenko (2014). We say that our partially exchangeable arrays are DAG-exchangeable since their partially exchangeable structure is governed by a collection of Directed Acyclic Graphs. More specifically, such a random array is indexed by $mathbb{N}^{|V|}$ for some DAG $G=(V,E)$, and its exchangeability structure is governed by the edge set $E$. We prove a representation theorem for such arrays which generalizes the Aldous-Hoover and Austin-Panchenko representation theorems.
Let $mathcal{T}$ be a rooted tree endowed with the natural partial order $preceq$. Let $(Z(v))_{vin mathcal{T}}$ be a sequence of independent standard Gaussian random variables and let $alpha = (alpha_k)_{k=1}^infty$ be a sequence of real numbers with $sum_{k=1}^infty alpha_k^2<infty$. Set $alpha_0 =0$ and define a Gaussian process on $mathcal{T}$ in the following way: [ G(mathcal{T}, alpha; v): = sum_{upreceq v} alpha_{|u|} Z(u), quad v in mathcal{T}, ] where $|u|$ denotes the graph distance between the vertex $u$ and the root vertex. Under mild assumptions on $mathcal{T}$, we obtain a necessary and sufficient condition for the almost sure boundedness of the above Gaussian process. Our condition is also necessary and sufficient for the almost sure uniform convergence of the Gaussian process $G(mathcal{T}, alpha; v)$ along all rooted geodesic rays in $mathcal{T}$.
We prove that the Beta random walk has second order cubic fluctuations from the large deviation principle of the GUE Tracy-Widom type for arbitrary values $upalpha>0$ and $upbeta>0$ of the parameters of the Beta distribution, removing previous restrictions on their values. Furthermore, we prove that the GUE Tracy-Widom fluctuations still hold in the intermediate disorder regime. We also show that any random walk in space-time random environment that matches certain moments with the Beta random walk also has GUE Tracy-Widom fluctuations in the intermediate disorder regime. As a corollary we show the emergence of GUE Tracy-Widom fluctuations from the large deviation principle for trajectories ending at boundary points for random walks in space (time-independent) i.i.d. Dirichlet random environment in dimension $d=2$ for a class of asymptotic behavior of the parameters.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
