Solving word equations

DOI10.1016/S0747-7171(89)80056-2zbMath0685.20039MaRDI QIDQ5916475

Habib Abdulrab, Jean-Pierre Pecuchet

Publication date: 1989

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

word equationsunification algorithmassociative unificationMakanin's algorithmpig-pug method

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Algorithms in computer science (68W99)

Related Items

Unification in partially commutative semigroups, Makanin's algorithm is not primitive recursive, Implementation of Makanin's Algorithm, Graph Logics with Rational Relations, Solvability of context equations with two context variables is decidable, Word unification and transformation of generalized equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre
• A proof of Ehrenfeucht's conjecture
• Equations in free semigroups
• Complete sets of unifiers and matchers in equational theories
• EQUATIONS IN A FREE GROUP
• Minimal and complete word unification
• Equations in Free Groups
• ON THE RANK OF COEFFICIENTLESS EQUATIONS IN FOUR UNKNOWNS IN A FREE SEMIGROUP