Generalized Bundled Fragments for First-Order Modal Logic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Generalized Bundled Fragments for First-Order Modal Logic

Résumé

When we bundle quantifiers and modalities together (as in ∃x□, ♢∀x etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting 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 [14], 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 ∀x∀y□, ∀x∃y♢ 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.
Fichier principal
Vignette du fichier
LIPIcs-MFCS-2022-70.pdf (854.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03765358 , version 1 (31-08-2022)

Licence

Paternité

Identifiants

Citer

Mo Liu, Anantha Padmanabha, R Ramanujam, Yanjing Wang. Generalized Bundled Fragments for First-Order Modal Logic. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Aug 2022, Vienna, Austria. pp.70:1--70:14, ⟨10.4230/LIPIcs.MFCS.2022.70⟩. ⟨hal-03765358⟩
67 Consultations
40 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More