Finite Model Theory of the Triguarded Fragment and Related Logics.
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
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
Original language | English |
---|---|
Title of host publication | 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021 |
Pages | 1-13 |
Number of pages | 13 |
ISBN (electronic) | 9781665448956 |
Publication status | Published - 29 Jun 2021 |
Peer-reviewed | Yes |
External IDs
Scopus | 85112209706 |
---|---|
Mendeley | 5d6a0c73-dfce-36ca-a00d-6a3413dc8a04 |