On Homogenous Models of Fluted Languages

We study the fluted fragment of first-order logic which is often viewed as a multi-variable non-guarded extension to various systems of description logics lacking role-inverses. In this paper we show that satisfiable fluted sentences (even under reasonable extensions) admit special kinds of “nice” models which we call globally/locally homogeneous. Homogeneous models allow us to simplify methods for analysing fluted logics with counting quantifiers and establish a novel result for the decidability of the (finite) satisfiability problem for the fluted fragment with periodic counting. More specifically, we will show that the (finite) satisfiability problem for the language is \({\rm Tower}\)-complete. If only two variable are used, computational complexity drops to \({\rm NExpTime}\)-completeness. We supplement our findings by showing that generalisations of fluted logics, such as the adjacent fragment, have finite and general satisfiability problems which are, respectively, \(\Pi^0_1\)- and \(\Sigma^0_1\)-complete. Additionally, satisfiability becomes \(\Sigma^1_1\)-complete if periodic counting quantifiers are permitted.

Daumantas Kojelis
Download Paper