Finite Model Theory of the Triguarded Fragment and Related Logics.
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
The Triguarded Fragment (TGF) is among the most expressive decidable fragments of first-order logic, subsuming both its two-variable and guarded fragments without equality. We show that the TGF has the finite model property (providing a tight doubly exponential bound on the model size) and hence finite satisfiability coincides with satisfiability known to be N2ExpTime-complete. Using similar constructions, we also establish 2ExpTime-completeness for finite satisfiability of the constant-free (tri)guarded fragment with transitive guards.
Details
Originalsprache | Englisch |
---|---|
Titel | 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021 |
Seiten | 1-13 |
Seitenumfang | 13 |
ISBN (elektronisch) | 9781665448956 |
Publikationsstatus | Veröffentlicht - 29 Juni 2021 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85112209706 |
---|---|
Mendeley | 5d6a0c73-dfce-36ca-a00d-6a3413dc8a04 |