• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Correction to: Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
October 1, 2026
HSE Researchers Show How Congenital Motor Disorders Affect Brain Development
Researchers from HSE University’s Institute for Cognitive Neuroscience have synthesised the findings of their previous studies on brain development in children with obstetric brachial plexus palsy and arthrogryposis. Their analysis shows that impaired motor function in early childhood not only limits children’s motor experience but also affects memory, categorical thinking, and information processing. The study has been published in Frontiers in Psychology.
October 1, 2026
Window into the Body: Scientists Develop Neural Network to Detect Risk of 15 Diseases from Retinal Images
Russian universities, with the participation of HSE University, Sber, and Z-union, have developed a neural network that can simultaneously assess the risk of 15 types of pathology from retinal photographs, including not only eye diseases but also cardiovascular conditions. The AI system can help clinicians detect potentially concerning changes at an early stage, identify signs reflecting the condition of retinal blood vessels, and determine whether a patient may need further examination. The paper has been published in Frontiers in Medicine.
September 30, 2026
'We Did Not Limit the Time for Questions'
The International Laboratory for Supercomputer Atomistic Modelling and Multi-Scale Analysis at HSE University held a major conference on molecular dynamics. Participants had the opportunity to attend all the presentations, while speakers were given as much time as they needed to answer questions. The HSE News Service interviewed Grigory Smirnov, Head of the Laboratory, and Genri Norman, Chief Research Fellow, about the conference preparations and the discussions it generated.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Correction to: Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter

Studia Logica. 2021.
Rybakov M., Shkatov D.
Language: English
DOI
Keywords: modal logicFirst-order intuitionistic logicfirst-order logic
Similar publications
Modal Products and Around
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
Graph Games and Logic Design. Recent Developments and Further Directions. (TREN, volume 66)
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
Advances in Modal Logic 2024. Short Papers
[б.и.], 2024.
The book contains short papers presented at AiML 2024. ...
Added: August 15, 2024
Advances in Modal Logic
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
Variations on the Kripke trick
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
Algorithmic properties of modal and superintuitionistic logics of monadic predicates over finite Kripke frames
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
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
On Interpretations in Buchi Arithmetics
Zapryagaev A., / Series arXiv "math". 2022.
Added: December 7, 2022
On Strictly Positive Fragments of Modal Logics with Confluence
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
Strictly balanced uniform hypergraphs and generalizations of Zero-One Law
Matushkin A. D., Popova S., Discrete Mathematics 2022 Vol. 345 No. 6 Article 112835
In this work we describe the spectra of all rational numbers that could be a density of a strictly balanced uniform hypergraph. We also introduce some specific constructions of strictly balanced uniform hypergraphs, and exploit them to generalize some results about Zero-One Law and Zero-One k-Law to the case of random uniform hypergraphs. ...
Added: June 29, 2022
Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
Rybakov M., Shkatov D., Logical Investigations 2021 Vol. 27 No. 2 P. 93–120
Доказывается неразрешимость логи QCTL и QLTL в языке с двумя переменными и одной одноместной предикатной буквой. ...
Added: January 24, 2022
Nāgārjunian-Yogācārian Modal Logic versus Aristotelian Modal Logic
Шуман А. Н., 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
Algorithmic properties of first-order superintuitionistic logics of finite Kripke frames in restricted languages
Rybakov M., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 494–522
We consider the effect of restricting the number of individual variables, as well as the number and arity of predicate letters, in languages of first-order predicate superintuitionistic logics of finite Kripke frames on the logics' algorithmic properties.  By a finite frame we mean a frame with a finite set of possible worlds. The languages we consider have no constants, function ...
Added: December 23, 2020
Modal logics with transitive closure: Completeness, decidability, filtration
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
Kripke incompleteness of first-order calculi with temporal modalities of CTL and near logics
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
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
Rybakov M., Shkatov D., , in: Десятые Смирновские чтения: материалы Междунар. науч. конф., Москва, 15–17 июня 2017 г.: М.: Современные тетради, 2017. P. 45–45.
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. ...
Added: October 7, 2019
Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter
Rybakov M., Shkatov D., Studia Logica 2019 Vol. 107 No. 4 P. 695–717
We prove that the positive fragment of fi rst-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 [QBL;QKC] and [QBL;QFL], where QKC ...
Added: October 2, 2019
Соответствие на счетных структурах и запросы к теориям
Zolin E., В кн.: Одиннадцатые Смирновские чтения по логике: материалы Международной научной конференции, 19 – 21 июня 2019, г. Москва.: М.: Современные тетради, 2019. С. 24–26.
В модальной теории соответствия [1, Sect. 3.5] говорят, что формула первого порядка с одной свободной переменной 𝑞(𝑥) сигнатуры {𝑅,=}, где 𝑅 – бинарный предикатный символ, соответствует модальной формуле 𝐴, если для любой шкалы Крипке 𝐹 = (𝑊,𝑅) и точки 𝑤 ∈ 𝑊, имеем: 𝐹 |= 𝑞(𝑤) ⇔ 𝐹,𝑤 |= 𝐴. Будем обозначать соответствие 𝑞(𝑥)!𝐴, следуя [4], где ...
Added: June 30, 2019
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit