Decidability of ordered fragments of FOL via modal translation

Hongkai Yin*, Matteo Pascucci

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

Abstract (may include machine translation)

We present a simplification and a modification of a method introduced by Herzig to prove the decidability of Quine’s ordered fragment of first-order logic. The method consists in an interpretation of quantifiers as modal operators. We show that our modification yields the decidability of two new ordered fragments of first-order logic, called the grooved fragment and the loosely grooved fragment, whose expressive power lies between Quine’s ordered fragment and the fluted fragment.

Original languageEnglish
JournalCEUR Workshop Proceedings
Volume3733
StatePublished - 2024
Event39th Italian Conference on Computational Logic, CILC 2024 - Rome, Italy
Duration: 26 Jun 202428 Jun 2024

Keywords

  • Decidability
  • Fragments of first-order logic
  • Modal logic
  • Tree model property

Fingerprint

Dive into the research topics of 'Decidability of ordered fragments of FOL via modal translation'. Together they form a unique fingerprint.

Cite this