13 found
Order:
  1.  11
    Complexity and Expressivity of Propositional Dynamic Logics with Finitely Many Variables.Mikhail Rybakov & Dmitry Shkatov - 2018 - Logic Journal of the IGPL 26 (5):539-547.
  2.  10
    Complexity of Finite-Variable Fragments of Propositional Modal Logics of Symmetric Frames.Mikhail Rybakov & Dmitry Shkatov - forthcoming - Logic Journal of the IGPL.
  3.  14
    Complexity of the Universal Theory of Modal Algebras.Dmitry Shkatov & Clint J. Van Alten - 2020 - Studia Logica 108 (2):221-237.
    We apply the theory of partial algebras, following the approach developed by Van Alten, to the study of the computational complexity of universal theories of monotonic and normal modal algebras. We show how the theory of partial algebras can be deployed to obtain co-NP and EXPTIME upper bounds for the universal theories of, respectively, monotonic and normal modal algebras. We also obtain the corresponding lower bounds, which means that the universal theory of monotonic modal algebras is co-NP-complete and the universal (...)
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  4.  16
    Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter.Mikhail Rybakov & Dmitry Shkatov - 2018 - Studia Logica 107 (4):695-717.
    We prove that the positive fragment of first-order intuitionistic logic in the language with two individual variables and a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable. This holds true regardless of whether we consider semantics with expanding or constant domains. We then generalise this result to intervals \ and \, where QKC is the logic of the weak law of the excluded middle and QBL and QFL are first-order counterparts of Visser’s basic and formal logics, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  19
    A General Method for Proving Decidability of Intuitionistic Modal Logics.Natasha Alechina & Dmitry Shkatov - 2006 - Journal of Applied Logic 4 (3):219-230.
  6.  10
    Computational Complexity for Bounded Distributive Lattices with Negation.Dmitry Shkatov & C. J. Van Alten - 2021 - Annals of Pure and Applied Logic 172 (7):102962.
    We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  4
    Correction to: Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter.Mikhail Rybakov & Dmitry Shkatov - 2022 - Studia Logica 110 (2):597-598.
    Direct download (3 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  8.  2
    On Independent Axiomatizability of Quasi-Normal Modal Logics.Igor Gorbunov & Dmitry Shkatov - forthcoming - Studia Logica:1-29.
    We give a negative solution to the problem, posed by A. Chagrov and M. Zakharyaschev, of whether every quasi-normal propositional modal logic can be axiomatized by an independent set of axioms, with the inference rules of Substitution and Modus Ponens.
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  9.  51
    Modal Logics for Reasoning About Infinite Unions and Intersections of Binary Relations.Natasha Alechina, Philippe Balbiani & Dmitry Shkatov - 2012 - Journal of Applied Non-Classical Logics 22 (4):275 - 294.
    (2012). Modal logics for reasoning about infinite unions and intersections of binary relations. Journal of Applied Non-Classical Logics: Vol. 22, No. 4, pp. 275-294. doi: 10.1080/11663081.2012.705960.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  10. Logics with an Existential Modality.Natasha Alechina & Dmitry Shkatov - 2006 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 31-48.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  4
    Undecidability of the Logic of Partial Quasiary Predicates.Mikhail Rybakov & Dmitry Shkatov - 2022 - Logic Journal of the IGPL 30 (3):519-533.
    We obtain an effective embedding of the classical predicate logic into the logic of partial quasiary predicates. The embedding has the property that an image of a non-theorem of the classical logic is refutable in a model of the logic of partial quasiary predicates that has the same cardinality as the classical countermodel of the non-theorem. Therefore, we also obtain an embedding of the classical predicate logic of finite models into the logic of partial quasiary predicates over finite structures. As (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12.  9
    Correction to: Complexity of the Universal Theory of Modal Algebras.Dmitry Shkatov & Clint J. Van Alten - 2021 - Studia Logica 109 (5):1175-1175.
    In the original publication of the article, the authors name were abbreviated as “D. Shkatov” and “C. J. Van Alten”. However it should be “Dmitry Shkatov” and “Clint J. Van Alten”. The original article has been corrected.
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  13.  4
    Logics with an Existential Modality.Natasha Alechina & Dmitry Shkatov - 2006 - In Guido Governatori, Ian Hodkinson & Yde Venema (eds.), Advances in Modal Logic, Volume 6. CSLI Publications. pp. 31-48.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation