Minimal and complete word unification
From MaRDI portal
Publication:3474892
DOI10.1145/78935.78938zbMath0697.68052OpenAlexW2123995178MaRDI QIDQ3474892
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/78935.78938
Symbolic computation and algebraic computation (68W30) Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40) Word problems (aspects of algebraic structures) (08A50)
Related Items
Unification in partially commutative semigroups, Generating languages by a derivation procedure for elementary formal systems, System Description: E.T. 0.1, Regular Patterns in Second-Order Unification, An algorithm for distributive unification, The word matching problem is undecidable for finite special string-rewriting systems that are confluent, Makanin's algorithm is not primitive recursive, An analysis of Makanin's algorithm deciding solvability of equations in free groups, Equations in free semigroups with involution and their relation to equations in free groups., Makanin's algorithm for word equations-two improvements and a generalization, Towards parametrizing word equations, Proving convergence of self-stabilizing systems using first-order rewriting and regular languages, Solving equations with sequence variables and sequence functions, 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, Graph unification and matching, Codes and equations on trees, Unnamed Item, Solving word equations, Flat matching, Unification problem in equational theories, On equality up-to constraints over finite trees, context unification, and one-step rewriting, On the relation between context and sequence unification, The hardness of solving simple word equations, On PSPACE generation of a solution set of a word equation and its applications, Solvability of context equations with two context variables is decidable, Word unification and transformation of generalized equations, \(\forall \exists^{5}\)-equational theory of context unification is undecidable
