License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.70
URN: urn:nbn:de:0030-drops-168684
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16868/
Go to the corresponding LIPIcs Volume Portal

Liu, Mo ; Padmanabha, Anantha ; Ramanujam, R. ; Wang, Yanjing

Generalized Bundled Fragments for First-Order Modal Logic

pdf-format:
LIPIcs-MFCS-2022-70.pdf (0.8 MB)

Abstract

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 [Anantha 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 ∀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.

BibTeX - Entry

@InProceedings{liu_et_al:LIPIcs.MFCS.2022.70,
  author =	{Liu, Mo and Padmanabha, Anantha and Ramanujam, R. and Wang, Yanjing},
  title =	{{Generalized Bundled Fragments for First-Order Modal Logic}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16868},
  URN =		{urn:nbn:de:0030-drops-168684},
  doi =		{10.4230/LIPIcs.MFCS.2022.70},
  annote =	{Keywords: bundled fragments, first-order modal logic, decidability, tableaux}
}

Keywords: bundled fragments, first-order modal logic, decidability, tableaux
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI