LIPIcs.MFCS.2022.70.pdf
- Filesize: 0.83 MB
- 14 pages
Document
Generalized Bundled Fragments for First-Order Modal Logic
Authors
Mo Liu 
,
Anantha Padmanabha ,
Yanjing Wang
-
Part of:
Volume:
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-08-22
File
Document Identifiers
Author Details
Acknowledgements
The authors thank the anonymous reviewers of MFCS2022 for their comments that improved the presentation of the paper.
Cite AsGet BibTex
Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang. Generalized Bundled Fragments for First-Order Modal Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.70
https://doi.org/10.4230/LIPIcs.MFCS.2022.70
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Modal and temporal logics
- Theory of computation → Logic and verification
Keywords
- bundled fragments
- first-order modal logic
- decidability
- tableaux
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Hajnal Andréka, István Németi, and Johan van Benthem. Modal languages and bounded fragments of predicate logic. J. Philos. Log., 27(3):217-274, 1998. URL: https://doi.org/10.1023/A:1004275029985.
- Francesco Belardinelli and Alessio Lomuscio. Quantified epistemic logics for reasoning about knowledge in multi-agent systems. Artif. Intell., 173(9-10):982-1013, 2009. URL: https://doi.org/10.1016/j.artint.2009.02.003.
- Francesco Belardinelli and Alessio Lomuscio. Interactions between knowledge and time in a first-order logic for multi-agent systems: Completeness results. J. Artif. Intell. Res., 45:1-45, 2012. URL: https://doi.org/10.1613/jair.3547.
-
Egon Börger, Erich Grädel, and Yuri Gurevich. The classical decision problem. Springer Science & Business Media, 2001.
-
Torben Braüner and Silvio Ghilardi. First-order modal logic. In P. Blackburn, J. van Benthem, and F. Wolter, editors, Handbook of Modal Logic, pages 549-620. Elsevier, 2007.
- Clare Dixon, Michael Fisher, Boris Konev, and Alexei Lisitsa. Practical first-order temporal reasoning. In Proceedings of TIME 2008, pages 156-163, 2008. URL: https://doi.org/10.1109/TIME.2008.15.
- Harald Ganzinger, Christoph Meyer, and Margus Veanes. The two-variable guarded fragment with transitive relations. In Proceedings of LICS ‘99, pages 24-34, 1999. URL: https://doi.org/10.1109/LICS.1999.782582.
- Ian Hodkinson, Frank Wolter, and Michael Zakharyaschev. Decidable fragment of first-order temporal logics. Ann. Pure Appl. Log., 106(1-3):85-134, 2000. URL: https://doi.org/10.1016/S0168-0072(00)00018-X.
- Ian Hodkinson, Frank Wolter, and Michael Zakharyaschev. Monodic fragments of first-order temporal logics: 2000-2001 A.D. In Robert Nieuwenhuis and Andrei Voronkov, editors, Proceedings of LPAR '01, volume 2250, pages 1-23. Springer, 2001. URL: https://doi.org/10.1007/3-540-45653-8_1.
- Ian Hodkinson, Frank Wolter, and Michael Zakharyaschev. Decidable and undecidable fragments of first-order branching temporal logics. In Proceedings LICS 2002, pages 393-402, 2002. URL: https://doi.org/10.1109/LICS.2002.1029847.
-
G. E. Hughes and M. J. Cresswell. A New Introduction to Modal Logic. Routledge, 1996.
- Mo Liu. On the decision problems of some bundled fragments of first-order modal logic. Master’s thesis, Peking University, 2019. URL: https://arxiv.org/abs/2201.02336.
- Mo Liu, Anantha Padmanabha, Ramaswamy Ramanujam, and Yanjing Wang. Are bundles good deals for FOML? CoRR, abs/2202.01581, 2022. URL: http://arxiv.org/abs/2202.01581.
- Anantha Padmanabha, R Ramanujam, and Yanjing Wang. Bundled Fragments of First-Order Modal Logic: (Un)Decidability. In Proceedings of FSTTCS 2018, volume 122, pages 43:1-43:20, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.43.
- Mikhail N. Rybakov and Dmitry Shkatov. Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter. Stud Logica, 107(4):695-717, 2019. URL: https://doi.org/10.1007/s11225-018-9815-7.
-
Moshe Y Vardi. Why is modal logic so robustly decidable? Technical report, Rice University, 1997.
- Yanjing Wang. A new modal framework for epistemic logic. In Proceedings of TARK 2017, pages 515-534, 2017. URL: https://doi.org/10.4204/EPTCS.251.38.
- Yanjing Wang. Beyond Knowing That: A New Generation of Epistemic Logics. In Outstanding Contributions to Logic, volume 12, pages 499-533. Springer Nature, 2018. URL: https://doi.org/10.1007/978-3-319-62864-6_21.
- Frank Wolter and Michael Zakharyaschev. Decidable fragments of first-order modal logics. J. Symb. Log., 66(3):1415-1438, 2001. URL: http://www.jstor.org/stable/2695115.