The Fluted Fragment with Transitive Relations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913357216350208 |
|---|---|
| author | Pratt-Hartmann, Ian Tendera, Lidia |
| author_facet | Pratt-Hartmann, Ian Tendera, Lidia |
| contents | We study the satisfiability problem for the fluted fragment extended with transitive relations. The logic enjoys the finite model property when only one transitive relation is available and the finite model property is lost when additionally either equality or a second transitive relation is allowed. We show that the satisfiability problem for the fluted fragment with one transitive relation and equality remains decidable. 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 (or two transitive relations and equality). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_11169 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The Fluted Fragment with Transitive Relations Pratt-Hartmann, Ian Tendera, Lidia Logic in Computer Science 03D15 F.4.1; F.2.2 We study the satisfiability problem for the fluted fragment extended with transitive relations. The logic enjoys the finite model property when only one transitive relation is available and the finite model property is lost when additionally either equality or a second transitive relation is allowed. We show that the satisfiability problem for the fluted fragment with one transitive relation and equality remains decidable. 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 (or two transitive relations and equality). |
| title | The Fluted Fragment with Transitive Relations |
| topic | Logic in Computer Science 03D15 F.4.1; F.2.2 |
| url | https://arxiv.org/abs/2006.11169 |