Finite Model Theory of the Triguarded Fragment and Related Logics

Emanuel KierońskiEmanuel Kieroński, Sebastian RudolphSebastian Rudolph

Emanuel Kieroński, Sebastian Rudolph
Finite Model Theory of the Triguarded Fragment and Related Logics
In IEEE, eds., Proceedings of the 36th Annual Symposium on Logic in Computer Science (LICS 2021), 1-13, 2021

Details
Bibtex

KurzfassungAbstract
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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{KR2021,
  author    = {Emanuel Kiero{\'{n}}ski and Sebastian Rudolph},
  title     = {Finite Model Theory of the Triguarded Fragment and Related Logics},
  editor    = {IEEE},
  booktitle = {Proceedings of the 36th Annual Symposium on Logic in Computer
               Science (LICS 2021)},
  year      = {2021},
  pages     = {1-13},
  doi       = {10.1109/LICS52264.2021.9470734}
}