No label defined (Q3819992)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4092757
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4092757

      Statements

      0 references
      0 references
      0 references
      0 references
      1988
      0 references
      matching
      0 references
      non-termination
      0 references
      semi-unification algorithm
      0 references
      Knuth-Bendix completion
      0 references
      term-rewriting system
      0 references
      decision procedure
      0 references
      [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.
      0 references

      Identifiers