{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:15:04Z","timestamp":1760080504771,"version":"3.40.5"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T00:00:00Z","timestamp":1619481600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A complete classification of the complexity of the local and global satisfiability problems for graded modal language over traditional classes of frames has already been established. By \u201ctraditional\u201d classes of frames, we mean those characterized by any positive combination of reflexivity, seriality, symmetry, transitivity, and the Euclidean property. In this paper, we fill the gaps remaining in an analogous classification of the graded modal language with graded converse modalities. In particular, we show its NE<jats:sc>xp<\/jats:sc>T<jats:sc>ime<\/jats:sc>-completeness over the class of Euclidean frames, demonstrating this way that over this class the considered language is harder than the language without graded modalities or without converse modalities. We also consider its variation disallowing graded converse modalities, but still admitting basic converse modalities. Our most important result for this variation is confirming an earlier conjecture that it is decidable over transitive frames. This contrasts with the undecidability of the language with graded converse modalities.<\/jats:p>","DOI":"10.1017\/s1471068421000065","type":"journal-article","created":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:17:40Z","timestamp":1619504260000},"page":"493-520","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Completing the Picture: Complexity of Graded Modal Logics with Converse"],"prefix":"10.1017","volume":"21","author":[{"given":"BARTOSZ","family":"BEDNARCZYK","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"EMANUEL","family":"KIERO\u0143SKI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1908-0827","authenticated-orcid":false,"given":"PIOTR","family":"WITKOWSKI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,4,27]]},"reference":[{"key":"S1471068421000065_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-5791-1"},{"key":"S1471068421000065_ref6","doi-asserted-by":"crossref","unstructured":"Chen, C. and Lin, I. 1994. The complexity of propositional modal theories and the complexity of consistency of propositional modal theories. In Logical Foundations of Computer Science, Third International Symposium, LFCS\u201994, St. Petersburg, Russia, July 11\u201314, 1994, Proceedings, 69\u201380.","DOI":"10.1007\/3-540-58140-5_8"},{"key":"S1471068421000065_ref20","first-page":"1399","article-title":"Undecidability of the transitive graded modal logic with converse","volume":"5","author":"Zolin","year":"2017","journal-title":"Journal of Logic and Computation 27"},{"key":"S1471068421000065_ref9","doi-asserted-by":"crossref","unstructured":"Gogacz, T. , Guti\u00e9rrez-Basulto, V. , Ib\u00e1\u00f1ez-Garca, Y. , Jung, J. C. and Murlak, F. 2019. On finite and unrestricted query entailment beyond SQ with number restrictions on transitive roles. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10\u201316, 2019. ijcai.org, 1719\u20131725.","DOI":"10.24963\/ijcai.2019\/238"},{"key":"S1471068421000065_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-5788-9"},{"key":"S1471068421000065_ref19","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/11.1.85"},{"key":"S1471068421000065_ref17","first-page":"1","article-title":"On the computational complexity of the numerically definite syllogistic and related logics","volume":"1","author":"Pratt-Hartmann","year":"2008","journal-title":"Bulletin of Symbolic Logic 14"},{"key":"S1471068421000065_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107050884"},{"key":"S1471068421000065_ref10","unstructured":"Guti\u00e9rrez-Basulto, V. , Ib\u00e1\u00f1ez-Garca, Y. A. and Jung, J. C. 2017. Number restrictions on transitive roles in description logics with nominals. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4\u20139, 2017, San Francisco, California, USA, 1121\u20131127."},{"key":"S1471068421000065_ref11","doi-asserted-by":"crossref","unstructured":"Kazakov, Y. and Pratt-Hartmann, I. 2009. A note on the complexity of the satisfiability problem for graded modal logics. In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11\u201314 August 2009, Los Angeles, CA, USA, 407\u2013416.","DOI":"10.1109\/LICS.2009.17"},{"volume-title":"The Complexity of Reasoning with Concrete Domains","year":"2002","author":"Lutz","key":"S1471068421000065_ref14"},{"key":"S1471068421000065_ref5","first-page":"71","volume-title":"Advances in Modal Logic 4, Papers from the Fourth Conference on \u201cAdvances in Modal Logic,\u201d Held in Toulouse, France, 30 September\u20132 October 2002","author":"Chagrov","year":"2002"},{"key":"S1471068421000065_ref12","doi-asserted-by":"crossref","unstructured":"Kazakov, Y. , Sattler, U. and Zolin, E. 2007. How many legs do I have? non-simple roles in number restrictions revisited. In Logic for Programming, Artificial Intelligence, and Reasoning, 14th International Conference, LPAR 2007, Yerevan, Armenia, October 15\u201319, 2007, Proceedings, 303\u2013317.","DOI":"10.1007\/978-3-540-75560-9_23"},{"volume-title":"Complexity Results and Practical Algorithms for Logics in Knowledge Representation","year":"2001","author":"Tobies","key":"S1471068421000065_ref18"},{"key":"S1471068421000065_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-2464(07)80004-8"},{"key":"S1471068421000065_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/9781139025355"},{"key":"S1471068421000065_ref7","first-page":"151","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3\u20135, 1971, Shaker Heights, Ohio, USA","author":"Cook","year":"1971"},{"key":"S1471068421000065_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/0206033"},{"key":"S1471068421000065_ref16","first-page":"133","article-title":"Complexity of the guarded two-variable fragment with counting quantifiers","volume":"1","author":"Pratt-Hartmann","year":"2007","journal-title":"Journal of Logic and Computation 17"},{"key":"S1471068421000065_ref2","first-page":"642","volume-title":"Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Rende, Italy, May 7\u201311, 2019, Proceedings","volume":"11468","author":"Bednarczyk","year":"2019"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068421000065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T06:48:36Z","timestamp":1630392516000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068421000065\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,27]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["S1471068421000065"],"URL":"https:\/\/doi.org\/10.1017\/s1471068421000065","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2021,4,27]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}