The unification problem for term rewriting systems(TRSs) is the problem of deciding, for a given TRS R and two terms M and N, whether there exists a substitution θ such that Mθ and Nθ are congruent modulo R (i.e., Mθ←→R{top}*). In this paper, the unification problem for confluent right-ground TRSs is shown to be decidable. To show this, the notion of minimal terms is introduced and a new unification algorithm of obtaining a substitution whose range is in minimal terms is proposed. Our result extends the decidability of unification for canonical (i.e., confluent and terminating) right-ground TRSs given by Hullot (1980) in the sense that the termination condition can be omitted. It is also exemplified that Hullot's narrowing technique does not work in this case. Our result is compared with the undecidability of the word (and also unification) problem for terminating right-ground TRSs.
展开▼
