2026-09-21T12:48:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25526 2026-09-05T19:19:23Z ddc:004 open_access

Random Models and Guarded Logic Fiuk, Oskar guarded fragment finite model property probabilistic method Building on ideas of Gurevich and Shelah for the Gödel Class, we present a new probabilistic proof of the finite model property for the Guarded Fragment of First-Order Logic. Our proof is conceptually simple and yields the optimal doubly-exponential upper bound on the size of minimal models. We precisely analyse the obtained bound, up to constant factors in the exponents, and construct sentences that enforce models of tightly matching size. The probabilistic approach adapts naturally to the Triguarded Fragment, an extension of the Guarded Fragment that also subsumes the Two-Variable Fragment. Finally, we derandomise the probabilistic proof by providing an explicit model construction which replaces randomness with deterministic hash functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oskar Fiuk 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.37 urn:nbn:de:0030-drops-255269 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.37 eng https://creativecommons.org/licenses/by/4.0/legalcode