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
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
0.8607791662216187
0 references
0.843443751335144
0 references
0.8419910669326782
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