2024/11/28 by Daumantas Kojelis, Kojelis, Daumantas
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #DNA and Biological Computing #Cellular Automata and Applications
paper · pdf · doi:10.48550/arxiv.2411.19084
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 T\small OWER-complete. If only two variable are used, computational complexity drops to \rm NE\small XPT\small IME-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, Π01- and Σ01-complete. Additionally, satisfiability becomes Σ11-complete if periodic counting quantifiers are permitted.