This volume contains papers presented at the first international workshop onword equations and related topics held at the University of T}bingen in October 1990. Word equations, the central topic of this annual workshop, lieat the intersection of several important areas of computer science, suchas unification theory, combinatorics on words, list processing, and constraint logic programming. The workshop is a forum where researchers fromthese different domains may present and discuss results and ideas, thereby supporting interaction and cross-fertilization between theoretical questions and practical applications. The volume collects papers which: - contain new and relevant results, - describe a new approach to a subject, or - give a survey of main developments in an area. Papers cover investigations on free groups, associative unification and Makanin's algorithm to decide the solvability of equations in free semigroups, general unification theory and its relationship to algebra and model theory, Thue systems, and finitely presented groups.
Author(s): G. S. Makanin (auth.), K. U. Schulz (eds.)
Series: Lecture Notes in Computer Science 572
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1992
Language: English
Pages: 264
Tags: Mathematical Logic and Formal Languages; Data Structures; Artificial Intelligence (incl. Robotics); Mathematical Logic and Foundations
Investigations on equations in a free group....Pages 1-11
An analysis of Makanin's algorithm deciding solvability of equations in free groups....Pages 12-60
Implementation of Makanin's Algorithm....Pages 61-84
Makanin's algorithm for word equations-two improvements and a generalization....Pages 85-150
Unification theory....Pages 151-170
Algebraic and logical aspects of unification....Pages 171-180
Model-theoretic aspects of unification....Pages 181-196
Complete equational unification based on an extension of the Knuth-Bendix completion procedure....Pages 197-209
Unification in varieties of completely regular semigroups....Pages 210-230
A note on confluent Thue systems....Pages 231-236
Confluence of one-rule Thue systems....Pages 237-246
Systems of equations over a finite set of words and automata theory....Pages 247-249
New systems of defining relations of the braid group....Pages 250-256
