The fluted fragment with transitive relations

Ian Pratt-hartmann, Lidia Tendera

Research output: Contribution to journalArticlepeer-review

12 Downloads (Pure)

Abstract

The fluted fragment is a fragment of first-order logic (without equality) in which, roughly speaking, the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that this fragment has the finite model property. We consider extensions of the fluted fragment with various numbers of transitive relations, as well as the equality predicate. In the presence of one transitive relation (together with equality), the finite model property is lost; nevertheless, we show that the satisfiability and finite satisfiability problems for this extension remain decidable. We also show that the corresponding problems in the presence of two transitive relations (with equality) or three transitive relations (without equality) are undecidable, even for the two-variable sub-fragment.
Original languageEnglish
Pages (from-to)103042
JournalAnnals of Pure and Applied Logic
Volume173
Issue number1
Early online date6 Sep 2021
DOIs
Publication statusPublished - 1 Jan 2022

Fingerprint

Dive into the research topics of 'The fluted fragment with transitive relations'. Together they form a unique fingerprint.

Cite this