The Fluted Fragment with TransitivityCitation formats

Standard

The Fluted Fragment with Transitivity. / Pratt-Hartmann, Ian; Tendera, Lidia.

2019. 18:1-18:15 Paper presented at 44th International Symposium on Mathematical Foundations of Computer Science, Aachen, Germany.

Research output: Contribution to conferencePaperpeer-review

Harvard

Pratt-Hartmann, I & Tendera, L 2019, 'The Fluted Fragment with Transitivity', Paper presented at 44th International Symposium on Mathematical Foundations of Computer Science, Aachen, Germany, 26/08/19 - 30/08/19 pp. 18:1-18:15. https://doi.org/10.4230/LIPIcs.MFCS.2019.18

APA

Pratt-Hartmann, I., & Tendera, L. (2019). The Fluted Fragment with Transitivity. 18:1-18:15. Paper presented at 44th International Symposium on Mathematical Foundations of Computer Science, Aachen, Germany. https://doi.org/10.4230/LIPIcs.MFCS.2019.18

Vancouver

Pratt-Hartmann I, Tendera L. The Fluted Fragment with Transitivity. 2019. Paper presented at 44th International Symposium on Mathematical Foundations of Computer Science, Aachen, Germany. https://doi.org/10.4230/LIPIcs.MFCS.2019.18

Author

Pratt-Hartmann, Ian ; Tendera, Lidia. / The Fluted Fragment with Transitivity. Paper presented at 44th International Symposium on Mathematical Foundations of Computer Science, Aachen, Germany.15 p.

Bibtex

@conference{0a8a3588be3d41b985af8c471a8249e6,
title = "The Fluted Fragment with Transitivity",
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.",
keywords = "First-Order logic, Decidability, Satisfiability, Transitivity, Complexity",
author = "Ian Pratt-Hartmann and Lidia Tendera",
year = "2019",
month = aug,
day = "20",
doi = "10.4230/LIPIcs.MFCS.2019.18",
language = "English",
pages = "18:1--18:15",
note = "44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 ; Conference date: 26-08-2019 Through 30-08-2019",

}

RIS

TY - CONF

T1 - The Fluted Fragment with Transitivity

AU - Pratt-Hartmann, Ian

AU - Tendera, Lidia

PY - 2019/8/20

Y1 - 2019/8/20

N2 - 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.

AB - 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.

KW - First-Order logic

KW - Decidability

KW - Satisfiability

KW - Transitivity

KW - Complexity

U2 - 10.4230/LIPIcs.MFCS.2019.18

DO - 10.4230/LIPIcs.MFCS.2019.18

M3 - Paper

SP - 18:1-18:15

T2 - 44th International Symposium on Mathematical Foundations of Computer Science

Y2 - 26 August 2019 through 30 August 2019

ER -