?
On existence of recursively-enumerable Kripke-complete first-order modal logics that are not Kripke complete with respect to a first-order definable class of frames
P. 45–45.
Rybakov M., Shkatov D.
We discuss an example of recursively-enumerable Kripke-complete first-order modal logics that are not Kripke complete with respect to a first-order definable class of frames.
Language:
English
In book
М.: Современные тетради, 2017.
Shehtman V. B., Gagarin A., , in: Graph Games and Logic Design. Recent Developments and Further Directions. (TREN, volume 66)Vol. 66.: Springer, 2026. Ch. 17 P. 419–450.
The chapter contains an overview of results on products of propositional modal logics and related constructions: semiproducts, Segerberg squares, and others. We focus mainly on axiomatizations, finite model property, and decidability; we also sketch connections with classical and modal predicate logics. In some cases we give ideas of proofs, especially of those using games. ...
Added: June 30, 2026
Springer, 2026.
This book presents established and new research on the close connections between graph games and systems of logic, particularly existing and newly designed modal logics. The volume utilizes two graph games – the sabotage game and the hide-and-seek game – to demonstrate the natural interplay between designing new graph games and exploring new kinds of ...
Added: June 30, 2026
[б.и.], 2024.
The book contains short papers presented at AiML 2024. ...
Added: August 15, 2024
College Publications, 2024.
Advances in Modal Logic (AiML) is an initiative founded in 1995 and aimed at presenting an up-to-date picture of the state of the art in modal logic and its many applications. It consists of a conference series together with volumes based on the conferences. The conference series is the main international forum at which research ...
Added: August 14, 2024
Rybakov M., Shkatov D., Studia Logica 2025 Vol. 113 P. 1–48
In the early 1960s, to prove undecidability of monadic fragments of sublogics of the predicate modal logic QS5 that include the classical predicate logic 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 ...
Added: December 2, 2023
Rybakov M., Shkatov D., Journal of Logic and Computation 2025 Vol. 35 No. 2 Article exad078
We show that the monadic modal logic of a single Kripke frame with finitely many possible worlds, but possibly infinite domains, is decidable. This holds true even for monadic multimodal logics with equality, both if equality interpreted as identity and if equality interpreted as congruence. ...
Added: November 3, 2023
Predicate counterparts of modal logics of provability: High undecidability and Kripke incompleteness
Rybakov M., Logic Journal of the IGPL 2024 Vol. 32 No. 3 P. 465–492
In this paper, the predicate counterparts, defined both axiomatically and semantically by means of Kripke frames, of the modal propositional logics GL, Grz, wGrz and their extensions are considered. It is proved that the set of semantical consequences on Kripke frames of every logic between QwGrz and QGL.3 or between QwGrz and QGrz.3 is Pi-1-1-hard even in languages with ...
Added: July 7, 2023
Valentin Shehtman, Annals of Pure and Applied Logic 2023 Vol. 174 No. 2 Article 103202
The paper studies completeness and incompleteness of modal predicate logics in
Kripke semantics, especially for logics of the form QL, minimal predicate extensions
of modal propositional logics. We show that QL is incomplete for a continual family
of logics above K + \Box(\Box p \rigtharrow p), in particular for well-known K5 and K45. On
the other hand, in some cases ...
Added: January 30, 2023
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Rybakov M., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595
We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...
Added: January 6, 2023
Kikot S., Kudinov A., Mathematics 2022 Vol. 10 No. 19 Article 3701
We axiomatize strictly positive fragments of modal logics with the confluence axiom. We consider unimodal logics such
as K.2, D.2, D4.2 and S4.2
with unimodal confluence $\Diamond\Box p \to \Box\Diamond p$
as well as the products of modal logics
in the set {K, D, T, D4, S4}, which contain bimodal confluence
$\Diamond_1\Box_2 p \to \Box_2\Diamond_1 p$.
We show that the impact ...
Added: October 10, 2022
Rybakov M., Shkatov D., Studia Logica 2021
Added: January 24, 2022
Zakharyaschev M., Kurucz A., Savateev Y. et al., Springer, 2021.
We prove that, similarly to known PSPACEPSPACE-completeness of recognising 𝖥𝖮(<)FO(<)-definability of the language 𝐿(𝔄)L(A) of a DFA 𝔄A, deciding both 𝖥𝖮(<,≡)FO(<,≡)- and 𝖥𝖮(<,𝖬𝖮𝖣)FO(<,MOD)-definability (corresponding to circuit complexity in AC0AC0 and ACC0ACC0) are PSPACEPSPACE-complete. We obtain these results by first showing that known algebraic characterisations of FO-definability of 𝐿(𝔄)L(A)can be captured by ‘localisable’ properties of the transition monoid of 𝔄A. Using our criterion, we then generalise the known proof ...
Added: November 6, 2021
Шуман А. Н., Journal of Indian Philosophy 2021 Vol. 49 P. 467–498
There are two different modal logics: the logic T assuming contingency and the logic K = assuming logical determinism. In the paper, I show that the Aristotelian treatise On Interpretation (Περί ερμηνείας, De Interpretatione) has introduced some modal-logical relationships which correspond to T. In this logic, it is supposed that there are contingent events. The Nāgārjunian treatise Īśvara-kartṛtva-nirākṛtiḥ-viṣṇoḥ-ekakartṛtva-nirākaraṇa has introduced some modal-logical relationships which correspond ...
Added: July 21, 2021
Kikot S., Shapirovsky I., Zolin E., , in: Advances in Modal LogicVol. 13.: College Publications, 2020. P. 369–388.
We give a sufficient condition for Kripke completeness of modal logics that have the transitive closure modality. More precisely, we show that if a modal logic admits what we call definable filtration, then its enrichment with the transitive closure modality (and the corresponding axioms) is Kripke complete; in addition, the resulting logic has the finite ...
Added: December 2, 2020
Rybakov M., Котикова Е. А., Logical Investigations 2015 Vol. 21 No. 1 P. 86–99
For an infinite class of calculi containing CTL and QCL, it is proved that they are Kripke incomplete. ...
Added: July 20, 2020
Rybakov M., Shkatov D., , in: Advances in Modal LogicVol. 12.: College Publications, 2018. P. 531–539.
It is well-known that every quanti ed modal logic complete with respect to a first-order defi nable class of Kripke frames is recursively enumerable. Numerous examples are also known of natural quanti ed modal logics complete with respect to a class of frames de ned by an essentially second-order condition which are not recursively enumerable. It is not, however, known if these ...
Added: October 6, 2019
Rybakov M., Чагрова Л. А., Программные продукты и системы 2018 Т. 31 № 3 С. 591–597
It is common to use the first-order language as a formal tool for describing properties of various (computational) structures. On the one hand, this language is well understood and easy to use; on the other, many questions that are im-portant from the applications point of view related to this language are algorithmically undecidable, i.e., cannot ...
Added: October 6, 2019
Shehtman V. B., , in: Larisa Maksimova on Implication, Interpolation, and Definability.: Cham: Springer, 2018. P. 245–296.
We establish a natural translation from word rewriting systems to strictly positive polymodal logics. Thereby, the latter can be considered as a generalization of the former. As a corollary we obtain examples of undecidable finitely axiomatizable strictly positive normal modal logics. The translation has its counterpart on the level of proofs: we formulate a natural ...
Added: September 21, 2018
Cham: Springer, 2018.
This edited volume focuses on the work of Professor Larisa Maksimova, providing a comprehensive account of her outstanding contributions to different branches of non-classical logic. The book covers themes ranging from rigorous implication, relevance and algebraic logic, to interpolation, definability and recognizability in superintuitionistic and modal logics. It features both her scientific autobiography and original ...
Added: September 20, 2018
Shehtman V. B., Shapirovsky I., , in: Advances in Modal LogicVol. 11.: L.: College Publications, 2016. P. 520–534.
According to the classical result by Segerberg and Maksimova, a modal logic containing K4 is locally tabular iff it is of finite height. The notion of finite height can also be defined for logics, in which the master modality is expressible (‘pretransitive’ logics). We observe that any locally tabular logic is pretransitive of finite height. Then we prove some ...
Added: September 20, 2018
Shehtman V. B., , in: Advances in Modal LogicVol. 12.: College Publications, 2018. P. 559–575.
We prove completeness for some normal modal predicate logics in the standard Kripke semantics with expanding domains. We consider quantified versions of propositional logics with the axiom of density plus some others (transitivity, confluence). The method of proof modifies the technique developed for other cases
(without density) by S. Ghilardi, G. Corsi and D. Skvorstov; but now we arrange the ...
Added: September 20, 2018