Convergence laws for extensions of first order logic with averaging

Conference item

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.

Authors: Benedikt, M; Adam-Day, S; Laurrari, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IEEE
• Host title: 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
• Pages: 818-830
• Publication date: 2025-06-25
• Acceptance date: 2025-04-07
• Event title: 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2025)
• Event location: Singapore
• Event website: https://lics.siglog.org/lics25/
• Event start date: 2025-06-23
• Event end date: 2025-06-26
• DOI: 10.1109/LICS65433.2025.00067
• EISBN: 9798331579005
• ISBN: 9798331579012
• Language: English
• Keywords: computer science; aggregates; focusing; logic; standards; convergence