一句话：将随机结构上一阶逻辑的零一律推广到半环语义，并刻画有限格半环中语句的几乎必然赋值及计算复杂度。
本文研究随机半环解释下的一阶逻辑语义。半环语义用交换半环中的值评估逻辑语句，而由半环元素上的概率分布诱导的随机半环解释推广了经典随机结构。作者考察 Glebskii 等人与 Fagin 的 0-1 律如何推广到半环语义。对于正半环，经典 0-1 律仅能推出每个一阶句子渐近地几乎必然取 0，或几乎必然只取非 0 值。通过更精细的分析，基于合适的扩展性质与一阶公式的代数表示，作者证明更强结果：对许多半环 K，FO(τ) 中的句子可按值 j ∈ K 划分为类 Φ_j，使 Φ_j 中每个句子在随机半环解释下几乎必然取值为 j。对有限或无限格半环，该划分坍缩为 Φ0、Φ1、Φε 三类，分别几乎必然取 0、1 与最小非零值 ε。文中还证明在有限格半环上计算一阶句子几乎必然赋值的问题是 Pspace 完全的。
Semiring semantics evaluates logical statements by values in some commutative semiring (K, +, ·, 0, 1). Random semiring interpretations, induced by a probability distribution on K, generalise random structures, and we investigate here the question of how classical results on first-order logic on random structures, most importantly the 0-1 laws of Glebskii et al. and Fagin, generalise to semiring semantics. For positive semirings, the classical 0-1 law implies that every first-order sentence is, asymptotically, either almost surely evaluated to 0 by random semiring interpretations, or almost surely takes only values different from 0. However, by means of a more sophisticated analysis, based on appropriate extension properties and on algebraic representations of first-order formulae, we can prove much stronger results. For many semirings K the first-order sentences in FO(τ) can be partitioned into classes (Φj)j ∈ K such that for each j ∈ K, every sentence in Φj evaluates almost surely to j under random semiring interpretations. Further, for finite or infinite lattice semirings, this partition actually collapses to just three classes Φ0, Φ1, and Φε, of sentences that, respectively, almost surely evaluate to 0, 1, and to the smallest value ε ≠ 0. For all other values j ∈ K we have that . The problem of computing the almost sure valuation of a first-order sentence on finite lattice semirings is Pspace-complete. Related version: All proofs can be found in the full version of this paper, available at https://arxiv.org/abs/2203.03425.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{GradelHNW22,
title = {Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics},
author = {Erich Grädel and Hayyan Helal and Matthias Naaf and Richard Wilke},
booktitle = {LICS},
year = {2022},
doi = {10.1145/3531130.3533358}
}