2026-07-23T13:20:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13648 2024-03-06T10:52:33Z ddc:004 open_access

On the Fluted Fragment (Invited Talk) Tendera, Lidia decidability fluted fragment first-order logic complexity satisfiability non-elementary The fluted fragment is a recently rediscovered decidable fragment of first-order logic whose history is dating back to Quine and the sixties of the 20th century. The fragment is defined by fixing simultaneously the order in which variables occur in atomic formulas and the order of quantification of variables; no further restrictions concerning e.g. the number of variables, guardedness or usage of negation apply. In the talk we review some motivation and the history of the fragment, discuss the differences between the fluted fragment and other decidable fragments of first-order logic, present its basic model theoretic and algorithmic properties, and discuss recent work concerning limits of decidability of its extensions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lidia Tendera 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.3 urn:nbn:de:0030-drops-136481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.3 eng https://creativecommons.org/licenses/by/4.0/legalcode