scientific article; zbMATH DE number 4092757

From MaRDI portal
Publication:3819992





[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.











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)