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
| CREATOR | Oskar Fiuk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05247