Ordered fragments of first-order logic

2021/03/14 by Jaakkola, Reijo
#F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2103.08046

Abstract

Using a recently introduced algebraic framework for the classification of fragments of first-order logic, we study the complexity of the satisfiability problem for several ordered fragments of first-order logic, which are obtained from the ordered logic and the fluted logic by modifying some of their syntactical restrictions.

Related

• The Adjacent Fragment and Quine's Limits of Decision
• On the Limits of Decision: the Adjacent Fragment of First-Order Logic
• Towards a Model Theory of Ordered Logics: Expressivity and Interpolation (Extended version)
• Fragments of first-order logic over infinite words
• Algebraic classifications for fragments of first-order logic and beyond