Makanin's algorithm for solving word equations with regular constraints

Diekert, Volker

Makanin's algorithm for solving word equations with regular constraints

dc.contributor.author	Diekert, Volker	de
dc.date.accessioned	1999-06-15	de
dc.date.accessioned	2016-03-31T07:58:08Z
dc.date.available	1999-06-15	de
dc.date.available	2016-03-31T07:58:08Z
dc.date.issued	1998	de
dc.date.updated	2013-06-19	de
dc.description.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.	en
dc.identifier.other	074006231	de
dc.identifier.uri	http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-4200	de
dc.identifier.uri	http://elib.uni-stuttgart.de/handle/11682/2436
dc.identifier.uri	http://dx.doi.org/10.18419/opus-2419
dc.language.iso	en	de
dc.relation.ispartofseries	Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;1998,2	de
dc.rights	info:eu-repo/semantics/openAccess	de
dc.subject.classification	Constraint <Künstliche Intelligenz> , Constraint-logische Programmierung	de
dc.subject.ddc	004	de
dc.title	Makanin's algorithm for solving word equations with regular constraints	en
dc.type	workingPaper	de
ubs.fakultaet	Fakultät Informatik, Elektrotechnik und Informationstechnik	de
ubs.institut	Institut für Formale Methoden der Informatik	de
ubs.opusid	420	de
ubs.publikation.typ	Arbeitspapier	de
ubs.schriftenreihe.name	Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik	de

Files

Original bundle

Now showing 1 - 1 of 1

Name:: 420_1.pdf
Size:: 393.95 KB
Format:: Adobe Portable Document Format

Download

Collections

05 Fakultät Informatik, Elektrotechnik und Informationstechnik