THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

1977/02/28 by G. S. Makanin · 6 citations
Decision Sciences · #Scheduling and Timetabling Solutions

paper · doi:10.1070/sm1977v032n02abeh002376

openalex publication_date 1977/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

In this paper we construct an algorithm recognizing the solvability of arbitrary equations in a free semigroup. Bibliography: 4 titles.

Cited by

• Finding patterns common to a set of strings
• Solving equations in strings: On Makanin's algorithm
• Undecidability of a Theory of Strings, Linear Arithmetic over Length, and String-Number Conversion
• Finite Countermodel Based Verification for Program Transformation (A Case Study)
• Complexity and expressive power of logic programming
• A Uniform Framework for Handling Position Constraints in String Solving (Technical Report)
• Gennady Makanin [wikipedia]