scientific article; zbMATH DE number 4092757
[For the entire collection see Zbl 0656.00031.] Semi-unification is a generalization of both matching and ordinary unification: for a given pair of terms s and t, two substitutions \(\rho\) and \(\sigma\) are sought such tha \(\rho (\sigma (s))=\sigma (t)\). Semi- unifiability can be used as a check for non-termination of a rewrite rule, but constructing a correct semi-unification algorithm has been an elusive goal; for example, an algorithm given by \textit{P. W. Purdom} jun. [Lect. Notes Comput. Sci. 256, 54-61 (1987; Zbl 0635.68019)], was incorrect. This paper presents a decision procedure for semi-unification based on techniques similar to those used in the Knuth-Bendix completion procedure. When its inputs are semi-unifiable, the procedure yields a canonical term-rewriting system from which substitutions \(\rho\) and \(\sigma\) are easily extracted. Though exponential in its computing time, the decision procedure can be improved to a polynomial time algorithm, as will be shown.
- On subsumption and semiunification in feature algebras
- Extending the type checker of Standard ML by polymorphic recursion
- Semi-unification of two terms in Abelian groups
- Relaxed unification -- proposal
- Upper bounds on height of terms in a solution of a semiunification problem
- Fast algorithms for uniform semi-unification
- Unification modulo nonnested recursion schemes via anchored semi-unification
- scientific article; zbMATH DE number 440473 (Why is no real title available?)
- scientific article; zbMATH DE number 4180772 (Why is no real title available?)
- Une charpente de semi-unification
- scientific article; zbMATH DE number 88941 (Why is no real title available?)
- A decidable case of the semi-unification problem
- An efficient decision algorithm for the uniform semi-unification problem. (Extended abstract)
- Semi-unification and generalizations of a particularly simple form
- scientific article; zbMATH DE number 10159 (Why is no real title available?)
- Termination of rule-based calculi for uniform semi-unification
- It is undecidable whether the Knuth-Bendix completion procedure generates a crossed pair
- Constructive many-one reduction from the halting problem to semi-unification
- Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version)
- Wanda -- a higher-order termination tool (system description)
- Semi-unification
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3819992)