• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Undecidability of QLTL and QCTL 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 8, 2026
HSE Experts Take Part in 23rd Annual Meeting of Valdai Discussion Club
The 23rd Annual Meeting of the Valdai Discussion Club was held from September 28 to October 1, 2026 under the theme ‘Responsibility for the Future: Limits of the Possible, or Limitless Possibilities?’ The forum brought together 120 experts from 40 countries, including representatives of China, the United States, India, Brazil, the United Kingdom, Germany, Egypt, Iran, and Japan.
October 7, 2026
‘Our Team Consists of True Leaders in Their Respective Academic Disciplines
The HSE International Centre of Decision Choice and Analysis studies a wide range of methods for analysing decision-making and possible scenarios for the development of natural, socio-economic, and political phenomena using various mathematical models. The application of advanced mathematical methods to forecasting helps to prevent negative outcomes and avoid erroneous decisions. The HSE News Service spoke to the centre’s director, Prof. Fuad Aleskerov, about its work.
October 6, 2026
International N5 Symposium ‘Neural Networks and Nonlinearity in Nizhny Novgorod Brings Together Scientists from Russia and Serbia
The International N5 Symposium ‘Neural Networks and Nonlinearity in Nizhny Novgorod’ was held at the Nizhny Novgorod House of Scientists from September 23 to 26. The event was organised by HSE University–Nizhny Novgorod and the Nizhny Novgorod House of Scientists, with the participation of Sberbank and the Institute of Physics Belgrade. The symposium was held for the second time: the first conference took place in 2025 and attracted considerable interest from the academic community.

 

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

?

Undecidability of QLTL and QCTL with two variables and one monadic predicate letter

Logical Investigations. 2021. Vol. 27. No. 2. P. 93–120.
Rybakov M., Shkatov D.
Research target: Mathematics
Language: English
Full text
DOI
Keywords: computational tree logicfirst-order logic
Similar publications
Modulational Instability and Wave Dynamics in the Rotated Modified Gardner–Whitham Equation
Flamarion M. V., Pelinovsky E., Chaos, Solitons and Fractals 2026 Vol. 213 No. 2 Article 119245
This article concerns the study of modulational instability in the rotated-modified Gardner–Whitham (rmGW) equation. This model incorporates both quadratic and cubic nonlinearities, similarly to the Gardner equation, while also retaining the fully dispersive character of the Whitham equation together with a large-scale dispersive term analogous to that in the Ostrovsky equation. Using a classical multiple-scale asymptotic expansion, we ...
Added: October 8, 2026
Space-Time Fluctuations in a Quasi-static Limit
Bernardin C., Gonçalves P., Olla S., Mathematical Physics Analysis and Geometry 2024 Vol. 27 No. 7
We consider the macroscopic limit for the space-time density fluctuations in the open symmetric simple exclusion in the quasi-static scaling limit. We prove that the distribution of these fluctuations converge to a gaussian space-time field that is delta correlated in time but with long-range correlations in space. ...
Added: October 6, 2026
To spike or not to spike: the whims of the Wonham filter in the strong noise regime
Bernardin C., Chhaibi R., Najnudel J. et al., Probability Theory and Related Fields 2026 Vol. 195 P. 1823–1875
We study the celebrated Shiryaev-Wonham filter (Wonham, W.M., in J. Soc. Ind. Appl. Math. 347–369, 1964) in its historical setup, where the hidden Markov jump process has two states. We are interested in the weak noise regime for the observation equation. Interestingly, this becomes a strong noise regime for the filtering equations. Earlier results of ...
Added: October 5, 2026
Цепная дробь Аски–Вильсона при qN=1
Ismailov A., Spiridonov V., Успехи математических наук 2026 Т. 81 № 5 С. 183–184
Получена новая формула для цепной дроби Аски–Вильсона в форме отношения двух  q-гипер-геометрических рядов. ...
Added: October 5, 2026
Explicit Formula for Inverse and Determinant in Geometric Algebras over Odd-dimensional Vector Spaces
Abdulkhaev K., Shirokov D., Advances in Applied Clifford Algebras 2026 Vol. 36 P. 1–21
In this paper, we present explicit formulas for the inverse and determinant in geometric (Clifford) algebras over vector spaces of dimension n = 7. The derivation of these formulas is made possible by generalizing the concept of conjugation to basis conjugation operations. We further develop a general method for constructing such formulas over odd-dimensional spaces ...
Added: October 4, 2026
On Practical Aspects of Constructing Quasi-Cyclic Subfield Subcodes of Dual Elliptic Codes and Their Application in McEliece-type Cryptosystems
Kuninets A., IEEE Transactions on Information Theory 2026 P. 1–1
In this work we study the applicability of Quasi-Cyclic Subfield Subcodes of Dual Elliptic (QC-SSDE) codes for integration into code-based cryptographic schemes. Detailed algorithms are provided for constructing parity-check matrices as well as block-circulant parity-check matrices for this family of codes, accompanied by empirical results that enable the construction of QC-SSDE codes with predetermined dimensions. ...
Added: October 3, 2026
Graphon spin systems as exactly solvable models
Medvedev G., Alexandrov Artem, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 2026 Vol. 114 Article 044102
Graphons are measurable functions used to describe the asymptotic behavior of convergent graph families. Originally motivated by problems in combinatorics and graph theory, graphons have found numerous applications in the modeling and analysis of dynamical processes on networks. In this work, we use graphons to formulate the Ising model on convergent graph sequences, which include ...
Added: October 2, 2026
Планетарное зацепление трилистника
Pochinka O., Baranov D., Nozdrinova E., Теоретическая и математическая физика 2026 Т. 229 № 1 С. 3–14
The Birman–Williams problem on describing the planetary link of a fibered knot K in S^3 has been partially solved. Using Nielsen's theory for the classification of periodic surface homeomorphisms and its close relationship with the theory of gradient-like diffeomorphisms, it is proved that the planetary link of the trefoil (the unique periodic fibered knot of genus ...
Added: October 2, 2026
A quantum–analogue formalism for modeling supraliminal information processing
Lubashevsky I., Lubashevskiy V., Physica D: Nonlinear Phenomena 2026 Vol. 498 Article 135441
We develop a novel cloud-function formalism describing the dynamical relationship between sensory-information processing in large-scale brain networks (supraliminal processing) and the content of the mental representation of an observed object. The formalism combines elements of neural field theory for large-scale neural activity with the spatial characteristics of perceived objects and their embedding in the environment ...
Added: October 2, 2026
Консервативные энтропийно и энергетически корректные разностные методы для одномерных квазигазодинамических систем уравнений
Zlotnik A., Математические заметки 2026 Т. 120 № 6 С. 1005–1009
Численным методам решения систем газодинамических уравнений посвящена обширная литература. Ранее было разработано и успешно апробировано специальное семейство симметричных по пространству  консервативных разностных методов, основанных на предварительной кинетической, точнее, квазигазодинамической (КГД), регуляризации этих уравнений. Актуальной задачей является построение численных методов, которые обладают не только свойством консервативности по массе, импульсу и полной энергии, но и удовлетворяют условиям энтропийной ...
Added: October 1, 2026
On some arithmetic conditions of recurrent sequences modulo prime p
Vyugin I. V., Sashadhar D., Algebra and Number Theory 2026 P. 1–10
We study the K-Fibonacci sequence Fp modulo prime p. Cardinalities of sets |Fp+Fp| and |Fp⋅Fp| are estimated. We present the method of estimating doubling constant of some m-dimensional recurrent sets in Fp. ...
Added: October 1, 2026
Long-time behaviour of dynamical systems driven by bounded mixing noises
Kuksin S., Dynamical Systems 2026
We study the mixing properties of discrete-time and continuous-time dissipative dynamical systems driven by bounded mixing random forces. The continuous-time systems are reduced to discrete-time random dynamical systems generated by time-one maps, so that the main analysis is carried out in the discrete setting. We introduce a class of mixing random forcings whose regular conditional distributions with ...
Added: October 1, 2026
Markovian reduction and exponential mixing in total variation for random dynamical systems
Kuksin S., Shirikyan A., Journal of Dynamics and Differential Equations 2026 P. 1098–1100
The paper deals with the problem of large-time behaviour of trajectories for discrete-time dynamical systems driven by a random noise. Assuming that the phase space is finite-dimensional and compact, and the noise is a Markov process with a transition probability satisfying some regularity hypotheses, we prove that all the trajectories converge to a unique measure ...
Added: October 1, 2026
Bounds on the derivatives of the log-cumulative distribution function of the multivariate normal distribution
Potanin B., Dolgikh S., Statistics and Probability Letters 2027 Article 110984
We derive bounds on the gradient and Hessian of the log-CDF, ln F(x), of the multivariate normal distribution. These bounds scale linearly and quadratically in ‖x‖ , respectively, with constants depending only on the covariance matrix. We demonstrate the usefulness of these bounds by proving asymptotic normality of the maximum-likelihood estimator of the multivariate probit ...
Added: October 1, 2026
Asymptotics of Spectrum and Quantum Averages of the Hydrogen Atom in a Magnetic Field Near the Upper Boundaries of Spectral Clusters
A. V. Pereskokov, Journal of Mathematical Sciences 2026 Vol. 302 No. 4 P. 531–545
We consider the Zeeman effect problem for the hydrogen atom in a magnetic field using irreducible representations of the Karasev–Novikova algebra with quadratic commutation relations. We find the asymptotics of a series of eigenvalues and the corresponding asymptotic eigenfunctions near the upper boundaries of spectral clusters. ...
Added: October 1, 2026
Simultaneous approximation of the score function and its derivatives by deep neural networks
Yakovlev K., Puchkin N., Journal of Complexity 2026 Vol. 97
We present a theory for simultaneous approximation of the score function and its derivatives, enabling the handling of data distributions with low-dimensional structure and unbounded support. Our approximation error bounds match those in the literature while relying on assumptions that relax the usual bounded support requirement. Crucially, our bounds are free from the curse of ...
Added: September 30, 2026
On Interpretations in Buchi Arithmetics
Zapryagaev A., / Series arXiv "math". 2022.
Added: December 7, 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
Correction to: Undecidability of First-Order Modal and Intuitionistic Logics with Two Variables and One Monadic Predicate Letter
Rybakov M., Shkatov D., Studia Logica 2021
Added: January 24, 2022
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
Алгоритмическая неразрешимость проблемы первопорядковой определимости формул логики ветвящегося времени
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
Соответствие на счетных структурах и запросы к теориям
Zolin E., В кн.: Одиннадцатые Смирновские чтения по логике: материалы Международной научной конференции, 19 – 21 июня 2019, г. Москва.: М.: Современные тетради, 2019. С. 24–26.
В модальной теории соответствия [1, Sect. 3.5] говорят, что формула первого порядка с одной свободной переменной 𝑞(𝑥) сигнатуры {𝑅,=}, где 𝑅 – бинарный предикатный символ, соответствует модальной формуле 𝐴, если для любой шкалы Крипке 𝐹 = (𝑊,𝑅) и точки 𝑤 ∈ 𝑊, имеем: 𝐹 |= 𝑞(𝑤) ⇔ 𝐹,𝑤 |= 𝐴. Будем обозначать соответствие 𝑞(𝑥)!𝐴, следуя [4], где ...
Added: June 30, 2019
On Temporal Properties of Nested Petri Nets
Dworzanski L. W., Frumin D. I., , in: Proceedings of the 6th Spring/Summer Young Researchers’ Colloquium on Software Engineering, SYRCoSE 2012.: Perm: -, 2012. P. 122–127.
Nested Petri nets is an extension of Petri net formalism with net tokens for modelling multi-agent distributed systems with complex structure. Temporal logics, such as CTL, are used to state requirements of software systems behaviour. However, in the case of nested Petri nets models, CTL is not expressive enough for specification of system behaviour. In ...
Added: September 20, 2012
  • 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