Minimal and complete word unification

DOI10.1145/78935.78938MaRDI QIDQ3474892zbMATH OpenOpenAlexFDO

Authors Joxan Jaffar

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

zbMATH Keywords

decision problemsunificationword problems

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Word problems (aspects of algebraic structures) (08A50) Formal languages and automata (68Q45) Symbolic computation and algebraic computation (68W30)

Recommendations

• Word unification and transformation of generalized equations
• Solving word equations
• Solving word equations
• Makanin's algorithm for word equations-two improvements and a generalization
• On PSPACE generation of a solution set of a word equation and its applications

Cited in

(34)

• On the relation between context and sequence unification
• Makanin's algorithm is not primitive recursive
• Unification problem in equational theories
• Word unification and transformation of generalized equations
• Unification in partially commutative semigroups
• Equations in free semigroups with involution and their relation to equations in free groups.
• Solvability of context equations with two context variables is decidable
• \(\forall \exists^{5}\)-equational theory of context unification is undecidable
• Uniform words
• Word equations in non-deterministic linear space
• On PSPACE generation of a solution set of a word equation and its applications
• Solving equations with sequence variables and sequence functions
• Word assembly through minimal forbidden words
• Generating languages by a derivation procedure for elementary formal systems
• What is essential unification?
• System description: E.T. 0.1
• Regular patterns in second-order unification
• scientific article; zbMATH DE number 1222432 (Why is no real title available?)
• scientific article; zbMATH DE number 1332632 (Why is no real title available?)
• Towards parametrizing word equations
• The word matching problem is undecidable for finite special string-rewriting systems that are confluent
• Graph unification and matching
• An algorithm for distributive unification
• scientific article; zbMATH DE number 7561688 (Why is no real title available?)
• The hardness of solving simple word equations
• Proving convergence of self-stabilizing systems using first-order rewriting and regular languages
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• Solving word equations
• Codes and equations on trees
• An analysis of Makanin's algorithm deciding solvability of equations in free groups
• Makanin's algorithm for word equations-two improvements and a generalization
• Unranked Nominal Unification
• Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general
• Flat matching

This page was built for publication: Minimal and complete word unification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3474892)