| Bibliography | Diekert, Volker: Makanin's Algorithm for Solving Word Equations with Regular Constraints.
University of Stuttgart, Faculty of Computer Science, Technical Report No. 1998/02.
43 pages, english.
|
|---|
| CR-Schema | F.2.2 (Nonnumerical Algorithms and Problems)
F.4.3 (Formal Languages)
|
|---|
| Keywords | Makanin; Makanins's Algorithm; Word Equations; Regular Constraints |
|---|
| Abstract | This report is a preliminary version of the twelfth chapter in the forthcoming book of M.~Lothaire {\em Algebraic Combinatorics on Words}. The aim is to describe a self-contained proof of a fundamental result of Makanin (1977), which solves the satisfiability problem of equations with constants over free monoids. The presentation of Makanin's algorithm is based on a generalization due to Schulz (1990), where Makanin's result is extended to the case where solutions are restricted by imposing regular constraints on the variables.
|
|---|
Full text and
other links | HTML (generated from PostScript)
|
|---|
| Department(s) | University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
|
|---|
| Entry date | April 7, 1998 |
|---|