Random expansions of finite structures with bounded degree

Vera Koponen

Published 2024-01-09Version 1

We consider finite relational signatures $\tau \subseteq \sigma$, a sequence of finite base $\tau$-structures $(\mathcal{B}_n : n \in \mathbb{N})$ the cardinalities of which tend to infinity and such that there is a fixed finite upper bound of the degree of (the Gaifman graph of) every $\mathcal{B}_n$. We let $\mathbf{W}_n$ be the set of all expansions to $\sigma$ of $\mathcal{B}_n$ we consider a probabilistic graphical model, a concept used in machine learning and artificial intelligence, to generate a probability distribution $\mathbb{P}_n$ on $\mathbf{W}_n$ for all $n$. We use a many-valued ``probability logic'' with truth values in the unit interval to express probabilities within probabilistic graphical models and to express queries on $\mathbf{W}_n$. This logic uses aggregation functions (e.g. the average) instead of quantifiers and it can express all queries (on finite structures) that can be expressed with first-order logic since the aggregation functions maximum and minimum can be used to express existential and universal quantifications, respectively. The main results concern asymptotic elimination of aggregation functions (the analogue of almost sure elimination of quantifiers for two-valued logics with quantifiers) and the asymptotic distribution of truth values of formulas (the analogue of logical convergence results for two-valued logics).