一句话：证明若干一阶逻辑收敛律可扩展到带平均聚合算子与Lipschitz连接词的实值逻辑。
论文研究随机结构上逻辑语句概率的收敛现象。经典结果包括常数边概率随机图中一阶逻辑语句概率收敛到0或1，以及稀疏随机图等模型中概率收敛但不一定到0/1。作者将一阶逻辑扩展到带聚合算子（平均算子变体）的逻辑：公式可构造实值项，并允许任意Lipschitz函数作为连接词。方法上，作者建立该实值聚合逻辑在随机图等标准随机结构模型上的收敛律，利用Lipschitz条件控制聚合和连接词对概率的影响。关键结果是证明若干已知一阶逻辑收敛律可推广到这一扩展框架，表明收敛现象在更丰富的聚合逻辑中依然成立。
For many standard models of random structure, first-order logic sentences exhibit a convergence phenomenon on random inputs. The most well-known example is for random graphs with constant edge probability, where the probabilities of first-order sentences converge to 0 or 1. In other cases, such as certain "sparse random graph" models, the probabilities of sentences converge, although not necessarily to 0 or 1. In this work we deal with extensions of first-order logic with aggregate operators, variations of averaging. These logics will consist of real-valued terms, and we allow arbitrary Lipschitz functions to be used as "connectives". We show that some of the well-known convergence laws extend to this setting.
DOI 原文 ·
@inproceedings{paperbot8666,
title = {Convergence Laws for Extensions of First-Order Logic with Averaging},
author = {Sam Adam-Day and Michael Benedikt and Alberto Larrauri},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00067}
}