Makanin's algorithm for word equations-two improvements and a generalization

DOI10.1007/3-540-55124-7_4zbMath1518.20005OpenAlexW1502428252MaRDI QIDQ6169560

Klaus U. Schulz

Publication date: 14 August 2023

Published in: Word Equations and Related Topics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55124-7_4

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

An SMT solver for regular expressions and linear arithmetic over string length ⋮ Non-structural subtype entailment in automata theory ⋮ Some independence results for equational unification ⋮ Linear second-order unification ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Word equations in the context of string solving ⋮ Solving trace equations using lexicographical normal forms ⋮ The word matching problem is undecidable for finite special string-rewriting systems that are confluent ⋮ Equational unification, word unification, and 2nd-order equational unification ⋮ On equations in free monoids and semigroups with restrictions on solutions ⋮ Solving word equations modulo partial commutations ⋮ Chain-Free String Constraints ⋮ Decidability of bounded higher-order unification ⋮ What Is Essential Unification? ⋮ Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general ⋮ Word equations in non-deterministic linear space ⋮ Z3str2: an efficient solver for strings, regular expressions, and length constraints ⋮ Regular expression order-sorted unification and matching ⋮ On the relation between context and sequence unification ⋮ On PSPACE generation of a solution set of a word equation and its applications ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equations in free semigroups
• Minimal and complete word unification
• RECOGNITION OF THE RANK OF EQUATIONS IN A FREE SEMIGROUP
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• A Machine-Oriented Logic Based on the Resolution Principle