6533b7d6fe1ef96bd1265e3b

RESEARCH PRODUCT

The Fluted Fragment with Transitivity

Ian Pratt-hartmannLidia Tendera

subject

FOS: Computer and information sciencesFirst-Order logicComputer Science - Logic in Computer ScienceTransitivity000 Computer science knowledge general worksComputer Science::Logic in Computer ScienceComputer ScienceDecidabilityComplexitySatisfiabilityLogic in Computer Science (cs.LO)

description

We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive relation is available. On the other hand we show that the satisfiability problem is undecidable already for the two-variable fragment of the logic in the presence of three transitive relations.

yearjournalcountryeditionlanguage
2019-06-21
10.4230/lipics.mfcs.2019.18https://www.research.manchester.ac.uk/portal/en/publications/the-fluted-fragment-with-transitivity(0a8a3588-be3d-41b9-85af-8c471a8249e6).html