2024/01/09 by Koponen, Vera · 1 citation
#03C13 03C10 03C80 03B70 68T27 60C05 #F.4.1 #FOS: Mathematics #G.3 #I.2.4 #Logic (math.LO)
paper · doi:10.48550/arxiv.2401.04802
We consider finite relational signatures τ⊆ σ, a sequence of finite base τ-structures (Bn : n ∈ ℕ) the cardinalities of which tend to infinity and such that, for some number Δ, the degree of (the Gaifman graph of) every Bn is at most Δ. We let Wn be the set of all expansions of Bn to σ and we consider a probabilistic graphical model, a concept used in machine learning and artificial intelligence, to generate a probability distribution ℙn on Wn 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 Wn. 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 (Bn : n ∈ ℕ) as above may be of independent interest.