Random Models and Guarded Logic This is the full version of a paper that appears in the Proceedings of STACS 2026.

Oskar Fiuk · 2026

Read Random Models and Guarded Logic This is the full version of a paper that appears in the Proceedings of STACS 2026. by Oskar Fiuk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05247.txt.

Description

Oskar Fiuk's 2026 paper gives a new proof, by a probabilistic method, of the finite model property for the Guarded Fragment of first-order logic. The Guarded Fragment restricts how variables may interact in logical formulas, keeping the logic decidable while still expressive. The finite model property says that any satisfiable sentence has a finite model, and Fiuk's proof builds on ideas of Gurevich and Shelah developed for the Gödel class.

The proof stays conceptually simple. It yields the best possible doubly exponential bound on minimal model size, analysed up to constant factors. Matching example sentences show the bound is tight, and the approach extends to the triguarded fragment. Such bounds set realistic expectations for automated reasoning tools built on guarded logics.

Catalog record

CREATOROskar Fiuk
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE129 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-05247

Browse the full library · About the Tower of Babel