Bibliograph.
Daten | Diekert, Volker: Makanin's Algorithm for Solving Word Equations with Regular Constraints.
Universität Stuttgart, Fakultät Informatik, Fakultätsbericht Nr. 1998/02.
43 Seiten, englisch.
|
|---|
| CR-Klassif. | F.2.2 (Nonnumerical Algorithms and Problems)
F.4.3 (Formal Languages)
|
|---|
| Keywords | Makanin; Makanins's Algorithm; Word Equations; Regular Constraints |
|---|
| Kurzfassung | 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.
|
|---|
Volltext und
andere Links | HTML (aus PostScript generiert)
|
|---|
| Abteilung(en) | Universität Stuttgart, Institut für Informatik, Theoretische Informatik
|
|---|
| Eingabedatum | 7. April 1998 |
|---|