ﻻ يوجد ملخص باللغة العربية
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).
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 o
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 neighb
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 exchangea
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 wit
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 restri