Document Open Access Logo

Two variable fragment of Term Modal Logic

Authors Anantha Padmanabha , R. Ramanujam

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.30.pdf
  • Filesize: 1.44 MB
  • 14 pages

Document Identifiers

Author Details

Anantha Padmanabha
  • Institute of Mathematical Sciences, HBNI, Chennai, India
R. Ramanujam
  • Institute of Mathematical Sciences, HBNI, Chennai, India

Acknowledgements

We thank Kamal Lodaya, Sreejith and Yanjing Wang for the insightful discussions. We also thank the anonymous referees for their comments and suggestions that helped better present the paper.

Cite AsGet BibTex

Anantha Padmanabha and R. Ramanujam. Two variable fragment of Term Modal Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.30

Abstract

Term modal logics (TML) are modal logics with unboundedly many modalities, with quantification over modal indices, so that we can have formulas of the form Exists y Forall x (Box_x P(x,y) implies Diamond_y P(y,x)). Like First order modal logic, TML is also "notoriously" undecidable, in the sense that even very simple fragments are undecidable. In this paper, we show the decidability of one interesting fragment, that of two variable TML. This is in contrast to two-variable First order modal logic, which is undecidable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Modal and temporal logics
Keywords
  • Term modal logic
  • satisfiability problem
  • two variable fragment
  • decidability

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. Journal of philosophical logic, 27(3):217-274, 1998. Google Scholar
  2. Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal Logic (Cambridge Tracts in Theoretical Computer Science). Cambridge University Press, 2001. Google Scholar
  3. Giovanna Corsi. A unified completeness theorem for quantified modal logics. The Journal of Symbolic Logic, 67(4):1483-1510, 2002. Google Scholar
  4. Kit Fine et al. Normal forms in modal logic. Notre Dame journal of formal logic, 16(2):229-237, 1975. Google Scholar
  5. Melvin Fitting and Richard L. Mendelsohn. First-Order Modal Logic (Synthese Library). Springer, 1999. Google Scholar
  6. Melvin Fitting, Lars Thalmann, and Andrei Voronkov. Term-Modal Logics. Studia Logica, 69(1):133-169, 2001. URL: https://doi.org/10.1023/A:1013842612702.
  7. Erich Grädel, Phokion G Kolaitis, and Moshe Y Vardi. On the decision problem for two-variable first-order logic. Bulletin of symbolic logic, 3(1):53-69, 1997. Google Scholar
  8. Erich Grädel and Martin Otto. On logics with two variables. Theoretical computer science, 224(1-2):73-113, 1999. Google Scholar
  9. MJ Hughes and GE Cresswell. A New Introduction to Modal Logic. Routledge. 1996. Routledge, 1996. Google Scholar
  10. Roman Kontchakov, Agi Kurucz, and Michael Zakharyaschev. Undecidability of first-order intuitionistic and modal logics with two variables. Bulletin of Symbolic Logic, 11(3):428-438, 2005. Google Scholar
  11. Barteld Kooi. Dynamic term-modal logic. In A Meeting of the Minds, pages 173-186, 2007. Google Scholar
  12. Saul A. Kripke. The Undecidability of Monadic Modal Quantification Theory. Mathematical Logic Quarterly, 8(2):113-116, 1962. URL: https://doi.org/10.1002/malq.19620080204.
  13. Michael Mortimer. On languages with two variables. Mathematical Logic Quarterly, 21(1):135-140, 1975. Google Scholar
  14. Eugenio Orlandelli and Giovanna Corsi. Decidable Term-Modal Logics. In 15th European Conference on Multi-Agent Systems, 2017. Google Scholar
  15. Anantha Padmanabha and R Ramanujam. The Monodic Fragment of Propositional Term Modal Logic. Studia Logica, pages 1-25, 2018. Google Scholar
  16. Anantha Padmanabha and R Ramanujam. Two variable fragment of Term Modal Logic. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.10260.
  17. Anantha Padmanabha, R Ramanujam, and Yanjing Wang. Bundled Fragments of First-Order Modal Logic: (Un)Decidability. In Sumit Ganguly and Paritosh Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), volume 122 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1-43:20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.43.
  18. Mikhail Rybakov and Dmitry Shkatov. Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter. Studia Logica, pages 1-23, 2017. Google Scholar
  19. Gennady Shtakser. Propositional Epistemic Logics with Quantification Over Agents of Knowledge. Studia Logica, 106(2):311-344, 2018. Google Scholar
  20. Gennady Shtakser. Propositional Epistemic Logics with Quantification Over Agents of Knowledge (An Alternative Approach). Studia Logica, August 2018. URL: https://doi.org/10.1007/s11225-018-9824-6.
  21. Yanjing Wang. A New Modal Framework for Epistemic Logic. In Proceedings Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2017, Liverpool, UK, 24-26 July 2017., pages 515-534, 2017. URL: https://doi.org/10.4204/EPTCS.251.38.
  22. Yanjing Wang and Jeremy Seligman. When Names Are Not Commonly Known: Epistemic Logic with Assignments. In Advances in Modal Logic Vol. 12 (2018): 611-628, College Publications, 2018 . Google Scholar
  23. Frank Wolter and Michael Zakharyaschev. Decidable fragments of first-order modal logics. The Journal of Symbolic Logic, 66(3):1415-1438, 2001. Google Scholar
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 Imprint Privacy Contact