We consider finite relational signatures $τ\subseteq σ$, a sequence of finite base $τ$-structures $(\mathcal{B}_n : n \in \mathbb{N})$ the cardinalities of which tend to infinity and such that, for some number $Δ$, the degree of (the Gaifman graph of) every $\mathcal{B}_n$ is at most $Δ$. We let $\mathbf{W}_n$ be the set of all expansions of $\mathcal{B}_n$ to $σ$ and 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. The structure theory that is developed for sequences $(\mathcal{B}_n : n \in \mathbb{N})$ as above may be of independent interest.

We consider logics with truth values in the unit interval $[0,1]$. Such logics are used to define queries and to define probability distributions. In this context the notion of almost sure equivalence of formulas is generalized to the notion of asymptotic equivalence. We prove two new results about the asymptotic equivalence of formulas where each result has a convergence law as a corollary. These results as well as several older results can be formulated as results about the relative asymptotic expressivity of inference frameworks. An inference framework $\mathbf{F}$ is a class of pairs $(\mathbb{P}, L)$, where $\mathbb{P} = (\mathbb{P}_n : n = 1, 2, 3, \ldots)$, $\mathbb{P}_n$ are probability distributions on the set $\mathbf{W}_n$ of all $\sigma$-structures with domain $\{1, \ldots, n\}$ (where $\sigma$ is a first-order signature) and $L$ is a logic with truth values in the unit interval $[0, 1]$. An inference framework $\mathbf{F}'$ is asymptotically at least as expressive as an inference framework $\mathbf{F}$ if for every $(\mathbb{P}, L) \in \mathbf{F}$ there is $(\mathbb{P}', L') \in \mathbf{F}'$ such that $\mathbb{P}$ is asymptotically total variation equivalent to $\mathbb{P}'$ and for every $\varphi(\bar{x}) \in L$ there is $\varphi'(\bar{x}) \in L'$ such that $\varphi'(\bar{x})$ is asymptotically equivalent to $\varphi(\bar{x})$ with respect to $\mathbb{P}$. This relation is a preorder. If, in addition, $\mathbf{F}$ is at least as expressive as $\mathbf{F}'$ then we say that $\mathbf{F}$ and $\mathbf{F}'$ are asymptotically equally expressive. Our third contribution is to systematize the new results of this paper and several previous results in order to get a preorder on a number of inference systems that are of relevance in the context of machine learning and artificial intelligence.

For a finite and relational signature σ and finite domain D we consider the set WD of all σ-structures with domain D. On WD a probability distribution is determined by a so-called parametrized probabilistic graphical model, a concept studied in statistical relational artificial intelligence. We also consider a many valued logic, denoted PLA, with truth values in the unit interval for expressing queries. PLA uses aggregation functions, for example the arithmetic mean, geometric mean, maximum and minimum, instead of quantifiers. In this setting we prove that every formula of PLA with only admissible aggregation functions is asymptotically equivalent to a formula without aggregation functions, as the domain size tends to infinity. A corollary of this is a probabilistic convergence law for PLA-formulas with only admissible aggregation functions.

We introduce a formal logical language, called conditional probability logic (CPL), which extends first-order logic and which can express probabilities, conditional probabilities and which can compare conditional probabilities. Intuitively speaking, although formal details are different, CPL can express the same kind of statements as some languages which have been considered in the artificial intelligence community. We also consider a way of making precise the notion of lifted Bayesian network, where this notion is a type of (lifted) probabilistic graphical model used in machine learning, data mining and artificial intelligence. A lifted Bayesian network (in the sense defined here) determines, in a natural way, a probability distribution on the set of all structures (in the sense of first-order logic) with a common finite domain D. Our main result (Theorem 3.14) is that for every “noncritical” CPL-formula φ(x¯) there is a quantifier-free formula φ⁎(x¯) which is “almost surely” equivalent to φ(x¯) as the cardinality of D tends towards infinity. This is relevant for the problem of making probabilistic inferences on large domains D, because (a) the problem of evaluating, by “brute force”, the probability of φ(x¯) being true for some sequence d¯ of elements from D has, in general, (highly) exponential time complexity in the cardinality of D, and (b) the corresponding probability for the quantifier-free φ⁎(x¯) depends only on the lifted Bayesian network and not on D. Some conclusions regarding the computational complexity of finding φ⁎ are given in Remark 3.17. The main result has two corollaries, one of which is a convergence law (and zero-one law) for noncritial CPL-formulas.

Abstract Let ${\cal M}$ be ternary, homogeneous and simple. We prove that if ${\cal M}$ is finitely constrained, then it is supersimple with finite SU-rank and dependence is k-trivial for some k < ω and for finite sets of real elements. Now suppose that, in addition, ${\cal M}$ is supersimple with SU-rank 1. If ${\cal M}$ is finitely constrained then algebraic closure in ${\cal M}$ is trivial. We also find connections between the nature of the constraints of ${\cal M}$ , the nature of the amalgamations allowed by the age of ${\cal M}$ , and the nature of definable equivalence relations. A key method of proof is to “extract” constraints (of ${\cal M}$ ) from instances of dividing and from definable equivalence relations. Finally, we give new examples, including an uncountable family, of ternary homogeneous supersimple structures of SU-rank 1.

Abstract Suppose that ${\cal M}$ is countable, binary, primitive, homogeneous, and simple. We prove that the SU-rank of the complete theory of ${\cal M}$ is 1 and hence 1-based. It follows that ${\cal M}$ is a random structure. The conclusion that ${\cal M}$ is a random structure does not hold if the binarity condition is removed, as witnessed by the generic tetrahedron-free 3-hypergraph. However, to show that the generic tetrahedron-free 3-hypergraph is 1-based requires some work (it is known that it has the other properties) since this notion is defined in terms of imaginary elements. This is partly why we also characterize equivalence relations which are definable without parameters in the context of ω-categorical structures with degenerate algebraic closure. Another reason is that such characterizations may be useful in future research about simple (nonbinary) homogeneous structures.

Abstract For integers l ≥ 1, d ≥ 0 we study (undirected) graphs with vertices 1, …, n such that the vertices can be partitioned into l parts such that every vertex has at most d neighbours in its own part. The set of all such graphs is denoted Pn (l, d). We prove a labelled first-order limit law, i.e., for every first-order sentence φ, the proportion of graphs in Pn (l, d) that satisfy φ converges as n → ∞. By combining this result with a result of Hundack, Prömel and Steger [12] we also prove that if 1 ≤ s1 ≤ … ≤ sl are integers, then Forb( ) has a labelled first-order limit law, where Forb( ) denotes the set of all graphs with vertices 1, …, n, for some n, in which there is no subgraph isomorphic to the complete (l + 1 )-partite graph with parts of sizes 1, s1, …, sl. In the course of doing this we also prove that there exists a first-order formula ξ, depending only on l and d, such that the proportion of ∈ Pn (l, d) with the following property approaches 1 as n → ∞: there is a unique partition of {1, …, n} into l parts such that every vertex has at most d neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by ξ.