文章基本信息

标题：The Fluted Fragment with Transitivity
本地全文：下载
作者：Ian Pratt-Hartmann ; Lidia Tendera
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-15
DOI：10.4230/LIPIcs.MFCS.2019.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：First-Order logic; Decidability; Satisfiability; Transitivity; Complexity