Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2419
Authors: Diekert, Volker
Title: Makanin's algorithm for solving word equations with regular constraints
Issue Date: 1998
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;1998,2
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-4200
http://elib.uni-stuttgart.de/handle/11682/2436
http://dx.doi.org/10.18419/opus-2419
Abstract: We give a self-contained proof of a fundamental result of Makanin (1977), which solves the satisfiability problem of equations with constants over free monoids. Our presentation of Makanin's algorithm is borrows Schulz (1992a), where Makanin's result is extended to the case where solutions are restricted by imposing regular constraints on the variables. This report appears (with minor modifications) as a chapter of the new book of M. Lothaire Algebraic Combinatorics on Words.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
420_1.pdf393,95 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.