Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.18
URN: urn:nbn:de:0030-drops-109626
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10962/
Pratt-Hartmann, Ian ; Tendera, Lidia
The Fluted Fragment with Transitivity
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{pratthartmann_et_al:LIPIcs:2019:10962,
author = {Ian Pratt-Hartmann and Lidia Tendera},
title = {{The Fluted Fragment with Transitivity}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {18:1--18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10962},
URN = {urn:nbn:de:0030-drops-109626},
doi = {10.4230/LIPIcs.MFCS.2019.18},
annote = {Keywords: First-Order logic, Decidability, Satisfiability, Transitivity, Complexity}
}
| Keywords: | First-Order logic, Decidability, Satisfiability, Transitivity, Complexity | |
| Seminar: | 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 20.08.2019 |
