{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T09:26:43Z","timestamp":1785490003354,"version":"3.56.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T00:00:00Z","timestamp":1686268800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["ANR-19-P3IA-0001"],"award-info":[{"award-number":["ANR-19-P3IA-0001"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            <jats:bold>First order modal logic (\ud835\udda5\ud835\uddae\ud835\uddac\ud835\uddab)<\/jats:bold>\n            is built by extending\n            <jats:bold>First Order Logic (\ud835\udda5\ud835\uddae)<\/jats:bold>\n            with modal operators. A typical formula is of the form\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\forall x \\exists y \\Box P(x,y)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Not only is \ud835\udda5\ud835\uddae\ud835\uddac\ud835\uddab undecidable, even simple fragments like that of restriction to unary predicate symbols, guarded fragment and two variable fragment, which are all decidable for \ud835\udda5\ud835\uddae become undecidable for \ud835\udda5\ud835\uddae\ud835\uddac\ud835\uddab. In this paper we study\n            <jats:bold>Term Modal logic (\ud835\uddb3\ud835\uddac\ud835\uddab)<\/jats:bold>\n            which allows modal operators to be indexed by terms. A typical formula is of the form\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\forall x \\exists y~\\Box _x P(x,y)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . There is a close correspondence between \ud835\uddb3\ud835\uddac\ud835\uddab and \ud835\udda5\ud835\uddae\ud835\uddac\ud835\uddab and we explore this relationship in detail in the paper.\n          <\/jats:p>\n          <jats:p>In contrast to \ud835\udda5\ud835\uddae\ud835\uddac\ud835\uddab, we show that the two variable fragment (without constants, equality) of \ud835\uddb3\ud835\uddac\ud835\uddab is decidable. Further, we prove that adding a single constant makes the two variable fragment of \ud835\uddb3\ud835\uddac\ud835\uddab undecidable. On the other hand, when equality is added to the logic, it loses the finite model property.<\/jats:p>","DOI":"10.1145\/3593584","type":"journal-article","created":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T12:09:34Z","timestamp":1681906174000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Decidable Fragment of First Order Modal Logic: Two Variable Term Modal Logic"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4265-5772","authenticated-orcid":false,"given":"Anantha","family":"Padmanabha","sequence":"first","affiliation":[{"name":"DI ENS, ENS, CNRS, PSL University, Inria, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6923-8330","authenticated-orcid":false,"given":"R.","family":"Ramanujam","sequence":"additional","affiliation":[{"name":"Azim Premji University, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004275029985"},{"key":"e_1_3_2_3_2","volume-title":"Modal Logic (Cambridge Tracts in Theoretical Computer Science)","author":"Blackburn Patrick","year":"2001","unstructured":"Patrick Blackburn, Maarten de Rijke, and Yde Venema. 2001. Modal Logic (Cambridge Tracts in Theoretical Computer Science). Cambridge University Press."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093891703"},{"key":"e_1_3_2_5_2","volume-title":"First-order Modal Logic","author":"Fitting Melvin","year":"2012","unstructured":"Melvin Fitting and Richard L. Mendelsohn. 2012. First-order Modal Logic. Vol. 277. Springer Science & Business Media."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013842612702"},{"key":"e_1_3_2_7_2","volume-title":"Quantification in Nonclassical Logic","author":"Gabbay Dov M.","year":"2009","unstructured":"Dov M. Gabbay, Dimitrij Skvortsov, and Valentin Shehtman. 2009. Quantification in Nonclassical Logic. Elsevier."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.2307\/421196"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00308-9"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/3.4.345"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1344862160"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1122038996"},{"key":"e_1_3_2_13_2","first-page":"173","volume-title":"A Meeting of the Minds","author":"Kooi Barteld","year":"2007","unstructured":"Barteld Kooi. 2007. Dynamic term-modal logic. In A Meeting of the Minds. 173\u2013186."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19620080204"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103305"},{"key":"e_1_3_2_16_2","first-page":"4161","volume-title":"IJCAI","author":"Liberman Andr\u00e9s Occhipinti","year":"2020","unstructured":"Andr\u00e9s Occhipinti Liberman and Rasmus Kr\u00e6mmer Rendsvig. 2020. Decidability results in first-order epistemic planning. In IJCAI. 4161\u20134167."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.70"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210118"},{"key":"e_1_3_2_19_2","first-page":"147","volume-title":"Multi-Agent Systems and Agreement Technologies","author":"Orlandelli Eugenio","year":"2017","unstructured":"Eugenio Orlandelli and Giovanna Corsi. 2017. Decidable term-modal logics. In Multi-Agent Systems and Agreement Technologies. Springer, 147\u2013162."},{"key":"e_1_3_2_20_2","volume-title":"Propositional Term Modal Logic","author":"Padmanabha Anantha","year":"2019","unstructured":"Anantha Padmanabha. 2019. Propositional Term Modal Logic. Ph.D. Dissertation. Institute of Mathematical Sciences, Homi Bhabha National Institute."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-018-9784-x"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-58771-3_2"},{"key":"e_1_3_2_23_2","volume-title":"44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)","author":"Padmanabha Anantha","year":"2019","unstructured":"Anantha Padmanabha and R. Ramanujam. 2019. Two variable fragment of term modal logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_24_2","volume-title":"38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Padmanabha Anantha","year":"2018","unstructured":"Anantha Padmanabha, R. Ramanujam, and Yanjing Wang. 2018. Bundled fragments of first-order modal logic: (Un) decidability. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science."},{"key":"e_1_3_2_25_2","first-page":"37","article-title":"Epistemic term-modal logic","author":"Rendsvig Rasmus K.","year":"2010","unstructured":"Rasmus K. Rendsvig. 2010. Epistemic term-modal logic. Proceedings of the 15th Student Session of the European Summer School in Logic, Language and Information (2010), 37\u201346.","journal-title":"Proceedings of the 15th Student Session of the European Summer School in Logic, Language and Information"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-018-9815-7"},{"key":"e_1_3_2_27_2","volume-title":"A Proof-Theoretic Study of Term-Sequence-Dyadic Deontic Logic and Common Sense Modal Predicate Logic","author":"Sawasaki Takahiro","year":"2021","unstructured":"Takahiro Sawasaki. 2021. A Proof-Theoretic Study of Term-Sequence-Dyadic Deontic Logic and Common Sense Modal Predicate Logic. Ph.D. Dissertation. Hokkaido University."},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/978-3-662-60292-8_18","volume-title":"International Workshop on Logic, Rationality and Interaction","author":"Sawasaki Takahiro","year":"2019","unstructured":"Takahiro Sawasaki, Katsuhiko Sano, and Tomoyuki Yamada. 2019. Term-sequence-modal logics. In International Workshop on Logic, Rationality and Interaction. Springer, 244\u2013258."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-017-9741-0"},{"key":"e_1_3_2_30_2","volume-title":"Term-modal Logic and Quantifier-free Dynamic Assignment Logic","author":"Thalmann Lars","year":"2000","unstructured":"Lars Thalmann. 2000. Term-modal Logic and Quantifier-free Dynamic Assignment Logic. Ph.D. Dissertation. Acta Universitatis Upsaliensis."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/031\/05"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.251.38"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/978-3-319-62864-6_21","volume-title":"Jaakko Hintikka on Knowledge and Game Theoretical Semantics","author":"Wang Yanjing","year":"2018","unstructured":"Yanjing Wang. 2018. Beyond knowing that: A new generation of epistemic logics. In Jaakko Hintikka on Knowledge and Game Theoretical Semantics. Springer, 499\u2013533."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2021.103071"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.2307\/2695115"},{"key":"e_1_3_2_36_2","unstructured":"Anantha Padmanabha. 2021. Relative expressive powers of first order modal logic and term modal logic. In Proceedings of the (ICLA\u201921) . Vol. 97. https:\/\/scholar.google.com\/citations?view_op=view_citation&hl=en&user=10ihAiIAAAAJ&citation_for_view10ihAiIAAAAJ:WF5omc3nYNoC."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593584","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3593584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:01Z","timestamp":1750178281000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593584"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,9]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3593584"],"URL":"https:\/\/doi.org\/10.1145\/3593584","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,9]]},"assertion":[{"value":"2022-05-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}