• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Notes on the computational aspects of Kripke’s theory of truth
  • 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
August 25, 2026
Scientists Develop Algorithm for More Reliable Processors in Data Centres
Researchers from HSE MIEM and Samara University have developed the LRF-3D algorithm to automatically bypass idle nodes in three-dimensional networks-on-chip. Thanks to its hierarchical architecture, the algorithm outperforms existing solutions in both speed and path accuracy, improving processor reliability for use in data centres, supercomputers, and AI computing. The source code and test results are publicly available.
August 24, 2026
Researchers Develop Method for Direct Generation of Regulatory DNA
Researchers at HSE University have developed a model for generating promoters and enhancers—DNA sequences that regulate gene activity. The model works directly with DNA nucleotides, without first transforming them into a continuous numerical representation. This solution could be useful for applications in synthetic biology and gene therapy. The study results were presented at the ICLR 2026 Workshop ‘Generative AI in Genomics (Gen^2): Barriers and Frontiers.’
August 21, 2026
Social Integration: At the Crossroads of Knowledge and Values
The International Laboratory for Social Integration Research (ILSIR) at HSE University studies the challenges faced by vulnerable groups and explores ways to help them participate fully in everyday life. To develop effective solutions, the laboratory’s researchers combine cutting-edge methods with practical fieldwork. In this interview with the HSE News Service, Laboratory Head Elena Iarskaia-Smirnova discusses the laboratory’s work.

 

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

?

Notes on the computational aspects of Kripke’s theory of truth

Studia Logica. 2017. Vol. 105. No. 2. P. 407–429.
Speranski S. O.

The paper contains a survey on the complexity of various truth hierarchies arising in Kripke’s theory. I present some new arguments, and use them to obtain a number of interesting generalisations of known results. These arguments are both relatively simple, involving only the basic machinery of constructive ordinals, and very general.

Language: English
DOI
Keywords: complexitytruthdependencegroundednessinductive definitions
Similar publications
Reasoning from hypotheses in *-continuous action lattices
Kuznetsov S., Pshenitsyn T., Speranski S. O., Journal of Symbolic Logic 2025 Article jsl.2025.16
The class of all ∗-continuous Kleene algebras, whose description includes an infinitary condition on the iteration operator, plays an important role in computer science. The complexity of reasoning in such algebras — ranging from the equational theory to the Horn one, with restricted fragments of the latter in between — was analyzed by Kozen (2002). This ...
Added: August 12, 2026
О замыкающих ординалах инфинитарных вероятностных исчислений
Speranski S. O., Математические заметки 2026 Т. 120 № 3 С. 470–483
We show that, in terms of closure ordinals, many infinitary calculi for ‘first-order’ logics of probability (i.e., for languages similar to those in [Abadi & Halpern 1994]) are as hard as possible: the corresponding closure ordinals coincide with the least non-constructive ordinal, denoted by $\omega_1^{\mathrm{CK}}$. ...
Added: August 12, 2026
On the complexity of first-order logics of probability
Speranski S. O., Grefenshtein A., Izvestiya. Mathematics 2026 Vol. 90 No. 4 P. 105–126
The article is concerned with Halpern's first-order logics of probability, which we denote by L_1 and L_2 – the first of these deals with probability distributions on the domain, while the second employs distributions on external sets of possible worlds. The proofs of [Abadi & Halpern 1994] of the complexity lower bound results for L_1 and L_2 ...
Added: August 12, 2026
A Big History Perspective on Complexity in Universal Evolution: Conclusions
David J. L., Leonid Grinin, Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 22 P. 585–608.
This collective monograph explores focus on complexity aspects in Big History against the background of complexity growth in the Universe, on our planet, and in biological, social, and cultural systems. Complexity growth is regarded as the connecting thread of evolutionary development and as a leading trend of Big History. The cosmic development chapters examine symmetries ...
Added: August 10, 2026
Human Evolution in the Complexity Growth Perspective: Toward Periodization of the Big History Biosocial Era
Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 13 P. 359–409.
We have undertaken an attempt to propose a periodization of the Big History Biosocial (Anthropogenesis) Era on the basis of the most recent scientific data. This periodization is complexity-based, that is, the boundaries of the identified epochs are marked with complexity jumps, that is, in our case, such phase transitions that result in significant increases ...
Added: August 10, 2026
Biological and Social Phases of Big History and Complexity Growth
Leonid Grinin, Alexander M., Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 12 P. 283–355.
In the first half of this chapter, Grinin et al. survey general similarities and differences between biological and social macroevolution. They undertake a systematic comparison between biological and social evolution at different levels of analysis and in various aspects, formulating a considerable number of general principles and rules of evolution, and working to develop a ...
Added: August 10, 2026
Complexity in Universal Evolution: A Big History Perspective—An Introduction
David J. L., Leonid Grinin, Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 1 P. 1–25.
Complexity is widely acknowledged as a foundational and pivotal concept in Big History, offering a unifying lens through which to examine the emergence and development of systems—from particles and galaxies to life, civilizations, and beyond. Yet, despite its centrality, major gaps remain in how we define, measure, and interpret complexity across different phases and scales. ...
Added: August 10, 2026
Ключевые понятия и идеи концепции бытийной истории Мартина Хайдеггера
Митлянская М. Б., Вестник Пермского университета. Философия. Психология. Социология 2020 № 3 С. 384–394
The paper explores Martin Heidegger’s concept of the «history of being». This concept was created in the philosopher’s late period. Critically analyzing the own paths of existential philosophy revealed in Being and Time, Heidegger gradually forms a spectrum of being-historical notions that will occupy a central po sition in contemplation after «the turn». The methods ...
Added: July 30, 2026
Анализ динамики оказания медицинской помощи при отказе от табака в наркологических организациях Российской Федерации в 2013-2023 гг.
Салагай О. О., Сахарова Г. М., Антонов Н. С. et al., Вопросы наркологии 2025 Т. 37 № 1 С. 27–43
In order to study the prevalence of signs of nicotine dependence among tobacco/nicotine users and the level of medical care for tobacco/nicotine use in addiction treatment organizations in the Russian Federation in 2013-2023, we have analyzed microdata from a sample observation of the health status of the population conducted in 2023. The analysis of the ...
Added: April 10, 2026
Relative Chaoticity of Natural Languages
Yerbolova A. S., Tomashchuk K., Kogan A. et al., Complexity 2026 Vol. 2026 No. 1 Article 5519690
Tis paper presents a novel approach to analyzing and grouping natural languages based on the degree of their chaoticity. It clusters 52 languages from 18 language families, according to the value of the entropy–complexity pair, to reveal the chaotic properties of semantic trajectories. Te obtained clusters appear to be closely correlated with the family of ...
Added: February 16, 2026
Реальность как философская проблема
Tulchinskii G. L., СПб.: Политех-Пресс, 2025.
This monograph is devoted to the analysis of reality, one of the most complex and polysemantic concepts in contemporary philosophy.It presents various approaches and methods for analyzing reality, including methodological research, historical-philosophical analysis, and socio-critical analysis. The monograph combines research from various fields of philosophical knowledge, including the philosophy of science, ontology, logic, epistemology, social philosophy, and aesthetics. ...
Added: January 29, 2026
Attribution of de re Propositional Attitudes as a Means of Persuasion
D.B. Tiskin, Frolov K., Herald of the Russian Academy of Sciences 2025 Vol. 95 No. 1 P. 26–33
By de re propositional attitude ascription for rhetorical purposes we will understand uttering a modal statement wherein the speaker deliberately uses a description of the object of an attitude that is knowingly unavailable for the attitude holder. As the existence of the de re rhetorical statement class is revealed, it gives rise to two questions, which will be the primary concern ...
Added: January 26, 2026
Complexity for probability logic with quantifiers over propositions
Speranski S. O., Journal of Logic and Computation 2013 Vol. 23 No. 5 P. 1035–1055
In the present article, the quantifiers over propositions are first introduced into the language for reasoning about probability, then the complexity issues for validity problems dealing with the corresponding hierarchy of probabilistic sentences are investigated. We prove, among other things, the $\Pi^1_1$-completeness for the general validity and also indicate the least level in the hierarchy ...
Added: December 27, 2025
Some new results in monadic second-order arithmetic
Speranski S. O., Computability 2015 Vol. 4 No. 2 P. 159–174
Added: December 27, 2025
Infinitary action logic with exponentiation
Kuznetsov S., Speranski S. O., Annals of Pure and Applied Logic 2022 Vol. 173 No. 2 Article 103057
We introduce infinitary action logic with exponentiation — that is, the multiplicative-additive Lambek calculus extended with Kleene star and with a family of subexponential modalities, which allow some of the structural rules (contraction, weakening, permutation). The logic is presented in the form of an infinitary sequent calculus. We prove cut elimination and, in the case ...
Added: December 26, 2025
Infinitary action logic with multiplexing
Kuznetsov S., Speranski S. O., Studia Logica 2023 Vol. 111 No. 2 P. 251–280
Infinitary action logic can be naturally expanded by adding exponential and subexponential modalities from linear logic. In this article we shall develop infinitary action logic with a subexponential that allows multiplexing (instead of contraction). Both non-commutative and commutative versions of this logic will be considered, presented as infinitary sequent calculi. We shall prove cut admissibility ...
Added: December 26, 2025
An ‘elementary’ perspective on reasoning about probability spaces
Speranski S. O., Logic Journal of the IGPL 2025 Vol. 33 No. 2 Article jzae042
This paper is concerned with a two-sorted probabilistic language, denoted by QPL, which contains quantifiers over events and over reals, and can be viewed as an elementary language for reasoning about probability spaces. The fragment of QPL containing only quantifiers over reals is a variant of the well-known ‘polynomial’ language from [Fagin et al. 1990, Section 6]. ...
Added: December 26, 2025
Sharpening complexity results in quantified probability logic
Speranski S. O., Logic Journal of the IGPL 2025 Vol. 33 No. 3 Article jzae114
We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of [Fagin et al. 1990]. One of these, denoted by QPL-e, is obtained by adding quantifiers over arbitrary events, and the other, denoted by p-QPL-e, uses quantifiers over propositional formulas — or equivalently, over events expressible by such formulas. The earlier proofs ...
Added: December 26, 2025
Complexity in Big History. An Introductory Exploration
LePoire D., Grinin L. E., Korotayev A., Journal of Big History 2025 Vol. 8 No. 3 P. 98–139
Building on foundational work in systems theory, thermodynamics, and evolutionary theory, this paper argues that complexity can serve as a conceptual bridge across disciplines. It explores the role of complexity dynamics in Big History through an integrative theoretical framework that spans physical, chemical, geological, biological, social, cognitive, and civilizational domains. By examining how complexity emerges, ...
Added: November 1, 2025
MIP Models and Complexity Results for DAG Scheduling in the Cloud
Yury Semenov, Oleg Sukhoroslov, , in: Mathematical Optimization Theory and Operations Research 24th International Conference, MOTOR 2025, Novosibirsk, Russia, July 7–11, 2025, ProceedingsVol. 15681.: Switzerland: Springer, 2025. P. 317–331.
Added: September 17, 2025
On the normality of the closures of spherical orbits
Arzhantsev I., Functional Analysis and Its Applications 1997 Vol. 31 No. 4 P. 278–280
Let a connected reductive group G act on a normal affine variety X with the generic stabilizer H, let the complexity of this action be one, and let the categorial quotient X//G be one-dimensional. Then the closure of any G-orbit in X is normal. ...
Added: June 13, 2025
Тарифный блеф Трампа
Gnidchenko A., Монокль 2024 № 50
Введение запретительных пошлин на поставку в США товаров из стран БРИКС — не более чем хлесткая вербальная угроза: по значительному числу товаров зависимость США от импорта из стран блока слишком высока ...
Added: December 13, 2024
  • 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