• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Two-sided unification is NP-complete
  • 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
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.
September 9, 2026
Scientists Train Neural Network to Generate Process Plans from 3D Models
Researchers at the HSE FCS AI and Digital Science Institute have developed CAD2TechSpec, a framework that converts 3D models of mechanical parts into machining process plans—step-by-step instructions for machine tools. The solution aims to reduce the time required for the design and preparation of technical process documentation in mechanical engineering, aircraft manufacturing, and other high-tech industries. The study findings have been published in PeerJ Computer Science.
September 7, 2026
Biologists Discover 'Molecular Fingerprint' of Preeclampsia
Researchers at HSE University employed a new method to model hypoxia in placental cells during pregnancies complicated by preeclampsia and identified molecular markers of tissue hypoxia. Since hypoxia is one of the key mechanisms underlying preeclampsia, these findings are important for a more accurate and timely diagnosis of the disease and for the development of effective treatment methods. The paper has been published in Placenta.

 

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

?

Two-sided unification is NP-complete

P. 55–61.
Zakharov V., Новикова Т. А.
It is generally accepted that to unify a pair of substitutions 1 and 2 means to find out a pair of substitutions 0 and 00 such that the compositions 10 and 200 are the same. Actually, unification is the problem of solving linear equations of the form 1X = 2Y in the semigroup of substitutions. But some other linear equations on substitutions may be also viewed as less common variants of unification problem. In this paper we introduce a two-sided unification as the process of bringing a given substitution 1 to another given substitution 2 from both sides by giving a solution to an equation X1Y = 2. Twosided unification finds some applications in software refactoring as a means for extracting instances of library subroutines in arbitrary pieces of program code. In this paper we study the complexity of two-sided unification and show that this problem is NP-complete by reducing to it the bounded tiling problem.
Language: English
Keywords: unificationalgorithmic complexitysubstitutiontiling problem

In book

Proceedings of the 28th International Workshop on Unification, UNIF 2014. Technical report no. 14-06 in RISC Report Series
Linz: Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, 2014.
Similar publications
Международная унификация и гармонизация частного права в сфере финансовых рынков
Klementiev A., Московский журнал международного права 2026 № 2 С. 190–202
INTRODUCTION. Concepts such as “harmonization” and “unification” are currently widely used in the legal field as methods for harmonizing legal regulation. Unlike domestic harmonization and unification, international legal convergence aims to eliminate contradictions in the laws of different states. The implementation of transnational harmonization and unification projects has been greatly facilitated by the activities of international ...
Added: July 30, 2026
Complexity of reasoning in Kleene algebra with sum-of-letters hypotheses
Stepan L. Kuznetsov, , in: Automated Reasoning: 13th International Joint Conference, IJCAR 2026, Lisbon, Portugal, July 26–29, 2026, Proceedings, Part II. (LNCS, volume 16689)Vol. 16689.: Cham: Springer, 2026. P. 161–177.
Kleene algebras are an algebraic abstraction of regular expressions, one of the central notions in computer science. While the equational theory of Kleene algebras is known to be decidable, reasoning from finite sets of hypotheses (Horn theory) quickly becomes undecidable. This happens even for simple classes of hypotheses which themselves do not involve Kleene star. ...
Added: July 26, 2026
Субституты нефтяного моторного топлива в легковом дорожном транспорте: риски для мирового спроса на нефть
Sinitsyn M., Весь мир, 2025.
The global transportation sector is undergoing a major transformation associated with the transition to a low-carbon economy and the expanded use of alternative energy sources. In recent decades, the substitution of petroleum-based motor fuels with their substitutes – primarily biofuels and electric power (electric vehicles) – in light-duty road transport has accelerated. Public policy at ...
Added: June 5, 2026
Влияние аксиомы связности на сложность модальной логики.
Kudinov A., Мясников К. М., Математика и теоретические компьютерные науки 2025 Т. 3 № 2 С. 58–84
The paper proves that for weakly transitive logics with the universal modality, whose formula satisfiability problem is in PSPACE, adding the connectedness axiom does not increase the complexity. Furthermore, an explicit algorithm solving this problem is presented. ...
Added: October 14, 2025
Автономия воли с эффектом против третьих лиц как средство гармонизации и унификации регулирования трансфера права собственности в МЧП
Олейников М. А., Leontieva E., Вестник Российского университета дружбы народов. Серия: Юридические науки 2025 № 4 (29) С. 1013–1030
Abstract. The absence of an effective way to solve the problem of transfer of ownership of movable property in cross-border transactions determines the relevance of the article. Lex rei sitae connecting factor does not cope with this task in case of mobile conflict. The use of the party autonomy can potentially be a tool to ...
Added: September 7, 2025
Are prime numbers and quadratic residues random?
Blank M., Discrete and Continuous Dynamical Systems 2025 Vol. 45 No. 11 P. 4186–4201
Appeals to randomness in various number-theoretic constructions appear regularly in modern scientific publications. Such famous names as V.I. Arnold, M. Katz, Ya.G. Sinai, and T. Tao are just a few examples. Unfortunately, all of these approaches rely on various, although often very non-trivial and elegant, heuristics. A new analytical approach is proposed to address the ...
Added: May 23, 2025
Принципы УНИДРУА, касающиеся применения положений о компенсации за прекращение (Principes d’UNIDROIT concernant l’applicabilité des clauses de résiliation-compensation), и их значение для правового регулирования рынка деривативов
Klementiev A., Fonotova O., Труды Института государства и права Российской академии наук 2024 Т. 19 № 6 С. 95–120
The Principles on the Operation of Close-Out Netting Provisions were developed by the International Institute for the Unification of Private Law (UNIDROIT) and published in 2013 (“UNIDROIT Principles on Close-Out Netting”). This act lays the foundation for improving national legal regulation with respect to the early termination of international derivatives transactions in bankruptcy and the ...
Added: February 6, 2025
Interactions Between Traditional and Reversed IT Adoption: How Incumbent Devices Affect Cross-Situational Specialization of New Entries
Agyapong Siaw C., Cadeaux J., Meissner D. et al., IEEE Transactions on Engineering Management 2024 Vol. 71 P. 10009–10025
This article proposes a cross-situational specialization framework for what, at its introduction, was a newer generation personal computer (PC) device (a tablet computer). With use as the basis for continuance adoption as the theoretical lens, this article explores how the tablet coexists as a substitute- and a complement-in-use with incumbent PC(s). To test a model ...
Added: September 27, 2024
Культурная глобализация: сценарии гомогенизации и гибридизации
Сехлеян С. А., Социология. Журнал Российской социологической ассоциации 2021 № 5 С. 165–170
CULTURAL GLOBALIZATION: HOMOGENIZATION AND HYBRIDIZATION SCENARIOS The phenomenon of globalization is a process that affects the material and spiritual aspects of life - economics, demography and politics, as well as culture. Based on this, globalization is an object of study not only in social sciences, but also in branches of knowledge - economics, politics, international relations ...
Added: July 16, 2024
Tiling problems and complexity of logics
Rybakov M., Serova D., , in: SCAN 2023 Semantical and Computational Aspects of Non-Classical Logics: Moscow + Online, June 13–17, 2023. Abstracts.: M.: ., 2023. P. 68–70.
We apply domino problems to give short proofs for some known theorems for the classical predicate logic and some modal logics. ...
Added: July 7, 2023
Modification and Optimization of Pollards's Factorization ρ-Method by Means of Recursive Algorithm of Number Calculation Factorization
Смирнов И. А., Разумов П. В., Болдырихин Н. В. et al., IEEE, 2019.
Investigations of cryptographic algorithms for today are very actually in connection with cybernetic attacks threat and necessity of information protection at the enterprises of various levels including the strategic appointment. The project implementation of John Pollard’s factorization ρ–method in the programming language C ++ is presented, which works faster than the standard algorithm by 27%. It can facilitate greatly the deciphering operation ...
Added: May 10, 2023
Реализация ρ–метода факторизации Джона Полларда на языке C++
Черкесова Л. В., Сафарьян О. А., Смирнов И. А., Молодой исследователь Дона 2018 Т. 3 (12) С. 111–121
The paper presents the project implementation of ρ-factor Pollard factorization in C ++, which works faster than the standard algorithm by 27%, which can significantly facilitate the work in deciphering and cryptanalysis of various ciphers such as RSA ...
Added: May 9, 2023
Commutative action logic
Stepan L. Kuznetsov, Journal of Logic and Computation 2023 Vol. 33 No. 6 P. 1437–1462
We prove undecidability and pinpoint the place in the arithmetical hierarchy for commutative action logic, i.e. the equational theory of commutative residuated Kleene lattices (action lattices), and infinitary commutative action logic, the equational theory of *-continuous commutative action lattices. Namely, we prove that the former is Σ01�10-complete and the latter is Π01�10-complete. Thus, the situation is the ...
Added: March 7, 2023
Российские приоритеты и подходы к решению проблем Корейского полуострова
Lukin A., Pugacheva O., Проблемы Дальнего Востока 2022 № 3 С. 9–27
The paper comprehensively examines Russia's foreign policy towards the Korean Peninsula. Its scientific relevance is defined by the unsettled issues on the Korean Peninsula, including the nuclear one, and the peninsula’s geographical proximity to the Russian Far East, the development of which is a priority task for Russia in the 21st century. The aim of ...
Added: June 27, 2022
The complexity of election problems with group-separable preferences
Faliszewski P., Karpov A., Obraztsova S., Autonomous Agents and Multi-Agent Systems 2022 Vol. 36 Article 18
We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height. We also show a polynomial-time algorithm for sampling group-separable elections uniformly at ...
Added: March 14, 2022
A \(\Pi^0_1\)-bounded fragment of infinitary action logic with exponential
Kuznetsov S., , in: Logic, Language, and Security. Essays Dedicated to Andre Scedrov on the Occasion of His 65th BirthdayIssue 12300.: Cham: Springer, 2020. P. 3–16.
Infinitary action logic is an extension of the multiplicative-additive Lambek calculus with Kleene iteration, axiomatized by an 𝜔-rule. Buszkowski and Palka (2007) show that this logic is \(\Pi^0_1\)-complete. As shown recently by Kuznetsov and Speranski, the extension of infinitary action logic with the exponential modality is much harder: \(\Pi^1_1\)-complete. The raise of complexity is of ...
Added: November 25, 2020
Development of Unified Morphological Models for the Research of Different Physical Processes in Electronic Systems
Yury N. Kofanov, Sotnikova S. Y., Skachko M. A., , in: Proceedings of the 2019 IEEE International Conference "Quality Management, Transport and Information Security, Information Technologies" (IT&QM&IS).: IEEE, 2019. P. 273–276.
The paper proposes morphological models for the analysis of complex electronic systems quality criterion. The reason for resorting to morphological models is the need to increase attention to improving the quality and reliability of electronic systems in the early design stages. At the same time, many difficulties of mathematical modeling of the investigated heterogeneous physical ...
Added: January 9, 2020
On graphs whose maximal cliques and stable sets intersect
Gurvich V., Andrade D. V., Boros E., , in: Optimization Problems in Graph TheoryBook 139.: Springer, 2018. P. 3–63.
We say that a graph G has the CIS-property and call it a CIS-graph if every maximal clique and every maximal stable set of G intersects. By definition, G is a CIS-graph if and only if the complementary graph \(\overline {G}\) is a CIS-graph. Let us substitute a vertex v of a graph G′ by a graph G″ and denote the obtained graph by G. It is also easy to ...
Added: October 10, 2018
Об одной теоретико-вероятностной модели Sponge-конструкции
Mironkin V., Обозрение прикладной и промышленной математики 2018 Т. 25 № 1 С. 3–8
The graph of internal states of Sponge construction and the relationship between internal states and elements of the output sequence are investigated. The methods of constructing collisions which use features of the cyclic structure of Sponge construction’s substitution are proposed. The general form of the corresponding collisions is described. ...
Added: April 27, 2018
Эволюция популизма в российской политике
Petrov N., Вестник общественного мнения. Данные. Анализ. Дискуссии 2017 № 3-4(125) С. 20–37
The analysis of populism as a phenomenon and its evolution in contemporary Russian politics ...
Added: March 10, 2018
The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions
Shitov Y., SIAM Review 2017 Vol. 59 No. 4 P. 794–800
Using elementary linear algebra, we develop a technique that leads to solutions of two widely known problems on nonnegative matrices. First, we give a short proof of the result by Vavasis stating that the nonnegative rank of a matrix is NP-hard to compute. This proof is essentially contained in the paper by Jiang and Ravikumar, ...
Added: November 9, 2017
О минимизации схем программ относительно логико-термальной эквивалентности
Zakharov V., Жайлауова Ш. Р., В кн.: Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.).: М.: МГУ, МАКС Пресс, 2017. С. 84–87.
Эффективная разрешимость проблемы л-т эквивалентности дает возможность приступить к решению задачи минимизации - построения схемы программ наименьшего размера, л-т эквивалентной заданной схеме. Чтобы отыскать ее решение, заметим, что модель вычислений стандартных схем программ сходна модели вычислений автоматов-преобразователей, работающих над полугруппами. Ранее был предложен метод минимизации автоматов-преобра\-зо\-вателей, работающих над упорядоченными левосократимыми полугруппами. В данной заметке мы ...
Added: October 22, 2017
Horn fragments of the Halpern-Shoham interval temporal logic
Zakharyaschev M., BRESOLIN D., KURUCZ A. et al., , in: ACM Transactions on Computational Logic (TOCL)Vol. 18. Issue 3.: NY: ACM, 2017. P. 1–39.
We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, the type of the underlying linear order (discrete or dense), and the type of semantics for the interval relations (reflexive or irreflexive). For example, we show that satisfiability of ...
Added: September 17, 2017
  • 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