2026-07-22T07:05:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10962 2024-03-06T10:46:55Z ddc:004 open_access

The Fluted Fragment with Transitivity Pratt-Hartmann, Ian Tendera, Lidia First-Order logic Decidability Satisfiability Transitivity Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ian Pratt-Hartmann and Lidia Tendera 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.18 urn:nbn:de:0030-drops-109626 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.18 eng https://creativecommons.org/licenses/by/3.0/legalcode