Mo Liu, Anantha Padmanabha, R. Ramanujam and Yanjing Wang
MFCS 2022
Publication year: 2022

When we bundle quantifiers and modalities together (as in $\exists x \Box$, $\Diamond \forall x$ etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting \textit{bundled} fragments of FOML. It is well-known that finding decidable fragments of \FOML is hard, but existing work shows that certain bundled fragments are decidable [Padmanabha et al 2018], without any restriction on the arity of predicates, the number of variables, or the modal scope. In this paper, we explore generalized bundles such as $\forall x\forall y \Box, \forall x\exists y \Diamond$ etc., and map the terrain with regard to decidability, presenting both decidability and undecidability results. In particular, we propose the loosely bundled fragment which is decidable over increasing domains and encompasses all known decidable bundled fragments.

Leave a Reply

Your email address will not be published.