10 found
Order:
  1.  10
    Predicate counterparts of modal logics of provability: High undecidability and Kripke incompleteness.Mikhail Rybakov - forthcoming - Logic Journal of the IGPL.
    In this paper, the predicate counterparts, defined both axiomatically and semantically by means of Kripke frames, of the modal propositional logics $\textbf {GL}$, $\textbf {Grz}$, $\textbf {wGrz}$ and their extensions are considered. It is proved that the set of semantical consequences on Kripke frames of every logic between $\textbf {QwGrz}$ and $\textbf {QGL.3}$ or between $\textbf {QwGrz}$ and $\textbf {QGrz.3}$ is $\Pi ^1_1$-hard even in languages with three (sometimes, two) individual variables, two (sometimes, one) unary predicate letters, and a single (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  23
    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.
  3.  20
    Complexity of finite-variable fragments of propositional modal logics of symmetric frames.Mikhail Rybakov & Dmitry Shkatov - forthcoming - Logic Journal of the IGPL.
  4.  28
    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 (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  5.  34
    Complexity of intuitionistic propositional logic and its fragments.Mikhail Rybakov - 2008 - Journal of Applied Non-Classical Logics 18 (2):267-292.
    In the paper we consider complexity of intuitionistic propositional logic and its natural fragments such as implicative fragment, finite-variable fragments, and some others. Most facts we mention here are known and obtained by logicians from different countries and in different time since 1920s; we present these results together to see the whole picture.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  6.  9
    Variations on the Kripke Trick.Mikhail Rybakov & Dmitry Shkatov - forthcoming - Studia Logica:1-48.
    In the early 1960s, to prove undecidability of monadic fragments of sublogics of the predicate modal logic $$\textbf{QS5}$$ QS 5 that include the classical predicate logic $$\textbf{QCl}$$ QCl, Saul Kripke showed how a classical atomic formula with a binary predicate letter can be simulated by a monadic modal formula. We consider adaptations of Kripke’s simulation, which we call the Kripke trick, to various modal and superintuitionistic predicate logics not considered by Kripke. We also discuss settings where the Kripke trick does (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  7.  9
    Complexity of intuitionistic and Visser's basic and formal logics in finitely many variables.Mikhail Rybakov - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 393-411.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  8.  15
    Complexity of finite-variable fragments of EXPTIME-complete logics ★.Mikhail Rybakov - 2007 - Journal of Applied Non-Classical Logics 17 (3):359-382.
    The main result of the present paper is that the variable-free fragment of logic K*, the logic with a single K-style modality and its “reflexive and transitive closure,” is EXPTIMEcomplete. It is then shown that this immediately gives EXPTIME-completeness of variable-free fragments of a number of known EXPTIME-complete logics. Our proof contains a general idea of how to construct a polynomial-time reduction of a propositional logic to its n-variable—and even, in the cases of K*, PDL, CTL, ATL, and some others, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  15
    Correction to: Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter.Mikhail Rybakov & Dmitry Shkatov - 2021 - Studia Logica 110 (2):597-598.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  10.  15
    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