• 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
  • 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
May 25, 2026
HSE Scientists Train Neural Network to 'Hear' Faults in Electric Motors
Researchers at the AI and Digital Science Institute of the HSE Faculty of Computer Science have developed a new method—the Signature-Guided Data Augmentation (SGDA) framework—that achieves 99% accuracy in motor fault detection and 86% accuracy in fault classification. The application of this approach can reduce industrial equipment repair costs, minimise downtime, and improve production safety. The study results have been published in Engineering Applications of Artificial Intelligence.
May 25, 2026
'The Humanities Serve as a Conscience'
Maria Mizernaia studies Soviet literature and the history of book publishing. In this interview for the HSE Young Scientists project, she discusses plans to publish a novel about besieged Leningrad, AI-provoked reflections on what it means to be human, and how novels can help satisfy our dopamine hunger.
May 25, 2026
Is It Possible to Predict a Citys Life Based on the Shape of Its Neighbourhoods?
Is it possible to predict, based on the configuration of streets and buildings, where a café will open or where traffic congestion will occur? Participants in the Spatial Analysis and Modelling of Urban Processes research and study group use open data and machine learning to identify universal patterns. Alexander Sheludkov and Eduard Somov discuss the purpose of comparing cities, the need for new forms of urban statistics, and how open data is transforming approaches to urban studies.

 

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
Влияние аксиомы связности на сложность модальной логики.
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
Эволюция Йорк-Антверпенских правил об общей аварии как источника международного частного морского права
Kasatkina A., Кобахидзе Д. И., Вестник Московского университета. Серия 11: Право 2016 № 4 С. 68–82
This article is devoted to the analysis of contemporary trends of reforming of York- Antwerp Rules on general average, about what in the literature, both Russian and foreign, is currently little information. In the study of international organization documents in the field of maritime trade were identified those problematic issues, on which new amendments to the York-Antwerp Rules ...
Added: February 12, 2017
О наследовании по праву представления
Rostovtseva N. V., Право. Журнал Высшей школы экономики 2016 № 3 С. 30–49
The paper studies the institute of inheriting per stripes. The main principles specified in the current civil code are in line with the provisions of the Digest of Laws of the Russian Empire. Inheriting per stripes should be differentiated from similar institutes (transmission or substitution). The main difference from transmission consists in the condition that ...
Added: November 27, 2016
Evaluation of the use of renewable energy sources and peat in rural municipal economy
Medvedeva E., Ryapin I., Urvatsev I. et al., Thermal Engineering (English translation of Teploenergetika) 2016 Vol. 63 No. 9 P. 611–620
This paper analyzes the cost-effectiveness of the use of renewable energy sources (RES) and peat in production of electric and heat energy in rural places of the country by comparing tariffs (prices) of energy versus total expenditures on generation of electric and heat energy when using RES and peat. The appraisal of a cost-effective scale ...
Added: October 9, 2016
  • 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