Dmitry Shkatov's publications

https://orcid.org/0000-0002-0559-1503

Journal articles:

Algorithmic properties of modal and superintuitionistic logics of monadic predicates over finite Kripke frames (with Mikhail Rybakov). To appear in Journal of Logic and Computation. Available here.

Variations on the Kripke trick (with Mikhail Rybakov). To appear in Studia Logica. Available here.

Extensions of Solovay's system S without independent sets of axioms (with Igor Gorbunov). Annals of Pure and Applied Logic, 175(1), 2024. Article 103360. Final version here.

Semiproducts, Products, and Modal Predicate Logics: Some Examples (with Valentin Shehtman). Doklady. Mathematics, 108(2), 2023, pp. 411--418. Prefinal draft here. Published version here.

Complexity function and complexity of validity of modal and superintuitionistic propositional logics (with Mikhail Rybakov). Journal of Logic and Computation, 33(7), 2023, pp. 1566–1595. Available here.

Complexity of the Universal Theory of Residuated Ordered Groupoids (with Clint J. Van Alten). Journal of Logic, Language and Information, 32(3), 2023, pp. 489--510. Final version here.

On independent axiomatizability of quasi-normal modal logics (with Igor Gorbunov). Studia Logica, 110(5), 2022, pp. 1189--1217. Final version here.

Complexity of finite-variable fragments of products with non-transitive modal logics (with Mikhail Rybakov). Journal of Logic and Computation, 32(5), 2022, pp. 853--870. Available here.

Complexity of finite-variable fragments of propositional temporal and modal logics of computation (with Mikhail Rybakov). Theoretical Computer Science, 925, 2022, pp. 45--60. Final version here.

Undecidability of the logic of partial quasiary predicates (with Mikhail Rybakov). Logic Journal of the IGPL, 30(3), 2022, pp. 519--533. Available here.

Undecidability of QLTL and QCTL with two variables and one monadic predicate letter (with Mikhail Rybakov). Logical Investigations, 27(2), 2021, pp. 93--120. Available here.

Algorithmic properties of first-order modal logics of linear Kripke frames in restricted languages (with Mikhail Rybakov). Journal of Logic and Computation, 31(5), 2021, pp. 1266--1288. Available here.

Computational complexity for bounded distributive lattices with negation (with Clint J. Van Alten). Annals of Pure and Applied Logic, 172(7), 2021, Article 102962. Final version here.

Algorithmic properties of first-order superintuitionistic logics of finite Kripke frames in restricted languages (with Mikhail Rybakov). Journal of Logic and Computation, 31(2), pp. 494-522, 2021. Available here.

Complexity of finite-variable fragments of products with K (with Mikhail Rybakov). Journal of Logic and Computation, 31(2), pp. 426-443, 2021. Available here.

Algorithmic properties of first-order modal logics of finite Kripke frames in restricted languages (with Mikhail Rybakov). Journal of Logic and Computation, 30(7), pp. 1305-1329, 2020. Available here.

Recursive enumerability and elementary frame definability in predicate modal logic (with Mikhail Rybakov). Journal of Logic and Computation, 30(2), pp. 549-560, 2020. Available here.

Complexity of the universal theory of modal algebras (with Clint J. Van Alten). Studia Logica, 108(2), pp. 221-237, 2020. Final version here.

Complexity of the universal theory of bounded residuated distributive lattice-ordered groupoids (with Clint J. Van Alten). Algebra Universalis, 80(3), article 36, 2019. Final version here.

Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter (with Mikhail Rybakov). Studia Logica, 107(4), pp. 695-717, 2019. Corrected version available at arXiv.

Complexity of finite-variable fragments of propositional modal logics of symmetric frames (with Mikhail Rybakov). Logic Journal of the IGPL, 27(1), pp. 60-68, 2019. Available here.

Complexity and expressivity of propositional dynamic logics with finitely many variables. (with Mikhail Rybakov) Logic Journal of the IGPL, 26(5), pp. 539-547, 2018. Available here.

Tableau-based decision procedure for the multiagent epistemic logic with all coalitional operators for common and distributed knowledge (with Mai Ajspur and Valentin Goranko). Logic Journal of the IGPL, 21(3), pp. 407-437, 2013. (pdf).

Modal logics for reasoning about infinite unions and intersections of binary relations (with Natasha Alechina and Philippe Balbiani). Journal of Applied Non-Classical Logics, 22(4), pp. 275-294, 2012. (pdf).

Tableau tool for testing satisfiability in LTL: Implementation and experimental analysis (with Valentin Goranko and Angelo Kyrilov). Electronic Notes in Theoretical Computer Science . Vol. 262. pp. 113-125, 2010. Available here.

Tableau-based decision procedures for logics of strategic ability in multi-agent systems (with Valentin Goranko). ACM Transactions on Computational Logic. Vol. 11(1), pp. 3:1-3:51, 2009. Available here.

A general method for proving decidability of intuitionistic modal logics (with Natasha Alechina). Journal of Applied Logic, 4(3), pp. 219-230, 2006. (pdf)

Conference papers:

Kripke (in)completeness of predicate modal logics with axioms of bounded alternativity (with Valentin Shehtman). Proceedings of FOMTL 2023. ESSLLI, 2023, pp. 26--29. pdf.

On algorithmic expressivity of finite-variable fragments of intuitionistic modal logics (with Mikhail Rybakov). Proceedings of SCAN 2023. Steklov Mathematical Institute, 2023, pp. 71--74. pdf.

Algorithmic complexity of monadic multimodal predicate logics with equality over finite Kripke framess (with Irina Agadzhanian and Mikhail Rybakov). Proceedings of SCAN 2023. Steklov Mathematical Institute, 2023, pp. 17--20. pdf.

Algorithmic properties of first-order modal logics of the natural number line in restricted languages (with Mikhail Rybakov). Nicola Olivetti, Rineke Verbrugge, Sara Negri and Gabriel Sandu (eds.) Advances in Modal Logic, Vol. 13. College Publications, 2020, pp. 523--539. (pdf)

Some prospects for semiproducts and products of modal logics (with Valentin Shehtman). Short Papers. Advances in Modal Logic 2020. (pdf)

Computational properties of the logic of partial quasiary predicates (with Mikhail Rybakov). Proceedings of SAICSIT2020. ACM, 2020. pp. 58--65. (pdf)

Trakhtenbrot theorem for classical languages with three individual variables (with Mikhail Rybakov). Proceedings of SAICSIT2019. ACM, 2019, article 19. Pre-final version here. Final version here.

On one-variable fragments of modal predicate logics (with Valentin Shehtman). Proceedings of SYSMICS2019. 2019. pp. 129-132. (pdf)

Complexity and expressivity of branching- and alternating-time temporal logics with finitely many variables. (with Mikhail Rybakov) Fischer B., Uustalu T. (eds) Theoretical Aspects of Computing - ICTAC 2018. Lecture Notes in Computer Science, Vol. 11187. Springer, 2018, pp. 396-414. Pre-final version available at arXiv. Final version here.

On complexity of propositional linear-time temporal logic with finitely many variables. (with Mikhail Rybakov) van Niekerk J., Haskins B. (eds). Proceedings of SAICSIT2018. ACM, 2018. pp. 313-316. Pre-final version available at arXiv. Final version here.

A recursively enumerable Kripke complete first-order logic not complete with respect to a first-order definable class of frames. (with Mikhail Rybakov) G. Bezhanishvili, G. D'Agostino, G. Metcalfe and T. Studer (eds.) Advances in Modal Logic, Vol. 12. College Publications, 2018. pp. 531-540. Available here.

Synthesizing strategies for homogenous multi-agent systems with incomplete information (with Jan Calta) Proceedings of 12th International Workshop on Computational Logic in Multi-Agent Systems, Lecture Notes in Artificial Intelligence, vol. 6814. Springer, 2011, pp. 122--137. (pdf)

Finding uniform strategies for multi-agent systems (with Jan Calta and Holger Schlingloff). Proceedings of 11th International Workshop on Computational Logic in Multi-Agent Systems, Lecture Notes in Artificial Intelligence, vol. 6245. Springer, 2010, pp. 135--152. (pdf)

Tableau-based decision procedure for full coalitional multiagent temporal-epistemic logic of branching time (with Valentin Goranko). Proceedings of the International Workshop on Formal Approaches to Multi-Agent Systems 2009 (FAMAS09). (pdf)

Tableau-based decision procedure for full coalitional multiagent temporal-epistemic logic of linear time (with Valentin Goranko). In Proceedings of 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 09). pp. 969--976. (pdf)

Tableu-based procedure for deciding satisfiability in the full coalitional multiagent epistemic logic (with Valentin Goranko). In S. Artemov, A. Nerode (editors). Logical Foundations of Computer Science 2009. Lecture Notes in Computer Science. Vol. 5407. Springer, 2009. pp. 197--213.

Tableau-based decision procedure for multi-agent epistemic logic with operators of commond and distributed knowledge (with Valentin Goranko). In A. Cerone, S. Gruner (editors). Proceedings of the 6th IEEE International Conference on Software Engineering and Formal Methods (SEFM2008). IEEE Computer Society Press, 2008. pp. 237--246.

Logics with modalities corresponding to infinite unions and intersections of accessibility relations (with Natasha Alechina and Philippe Balbiani). In Proceedings of International Workshop on Hybrid Logic 2007 (HyLo 2007). Dublin, 2007.

Logics with an existential modality (with Natasha Alechina). In G. Governatori et al. (eds.) Advances in Modal Logic, vol. 6. College Publications, 2006, pp. 31-48. (pdf)

On decidability of intuitionistic modal logics (with Natasha Alechina). In Proceeding of Methods for Modalities 3 (M4M2003). Nancy, France, 2003. (pdf)