Document Open Access Logo

Generalized Bundled Fragments for First-Order Modal Logic

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

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.70.pdf
  • Filesize: 0.83 MB
  • 14 pages

Document Identifiers

Author Details

Mo Liu
  • LORIA, Unviersity of Lorraine, Nancy, France
Anantha Padmanabha
  • DI ENS, École Normale Supérieure, Université PSL, CNRS, Inria, Paris, France
R. Ramanujam
  • Institute of Mathematical Sciences, HBNI, Chennai, India (Retired)
  • Azim Premji University, Bengaluru (Visiting)
Yanjing Wang
  • Department of Philosophy, Peking University, Beijing, China

Funding

This work is supported by NSSF grant 19BZX135.
  • Padmanabha, Anantha: The author is funded by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d’avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).

Acknowledgements

The authors thank the anonymous reviewers of MFCS2022 for their comments that improved the presentation of the paper.

Cite As Get 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

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)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. 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.
  2. 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.
  3. 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.
  4. Egon Börger, Erich Grädel, and Yuri Gurevich. The classical decision problem. Springer Science & Business Media, 2001. Google Scholar
  5. 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. Google Scholar
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. G. E. Hughes and M. J. Cresswell. A New Introduction to Modal Logic. Routledge, 1996. Google Scholar
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. Moshe Y Vardi. Why is modal logic so robustly decidable? Technical report, Rice University, 1997. Google Scholar
  17. 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.
  18. 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.
  19. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact