Paper: Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property (at LICS 2026)
Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.40
Abstract
Recently, symbolic structures were proposed as finite representations of potentially infinite first-order structures, where Linear Integer Arithmetic terms and formulas define the domain and interpretations of a structure. We generalize symbolic structures to use any base theory that admits a standard model. Symbolic structures induce a symbolic model property, which holds for a fragment of first-order logic if every satisfiable formula in the fragment has a symbolic model. The symbolic model property implies decidability, since the model-checking problem for symbolic structures is decidable. We use the symbolic model property to prove decidability for several fragments that extend the fragment of stratified formulas, relaxing the quantifier-alternation constraints by allowing one sort to have self-looping functions, under certain restrictions. To establish the symbolic model property for these fragments we construct a symbolic model for a formula from an arbitrary model. The construction and its correctness are proved in a generic fashion, which may be instantiated to other similarly restricted fragments.
BibTeX
@InProceedings{EladShoham-DecidabilityResults,
author = {Neta Elad and Sharon Shoham},
title = {Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property},
booktitle = {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
year = {2026},
month = {July},
pages = {40:1--40:27},
location = {Lisbon, Portugal},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.LICS.2026.40}
}
