Well limit behaviors of term rewriting systems

摘要

The limit behaviors of computations have not been fully explored. It is necessary to consider such limit behaviors when we consider the properties of infinite objects in computer science, such as infinite logic programs, the symbolic solutions of infinite polynomial equations. Usually, we can use finite objects to approximate infinite objects, and we should know what kinds of infinite objects are approximable and how to approximate them effectively. A sequence {R k : k ε ω} of term rewriting systems has the well limit behavior if under the condition that the sequence has the set-theoretic limit or the distance-based limit, the sequence {Th(R k ): k ε ω} of corresponding theoretic closures of R k has the set-theoretic or distance-based limit, and lim k→∞ Th(R k ) is equal to the theoretic closure of the limit of {R k : k ε ω}. Two kinds of limits of term rewriting systems are considered: one is based on the set-theoretic limit, the other is on the distance-based limit. It is proved that given a sequence {R k : κ ε ω} of term rewriting systems R k , if there is a well-founded ordering ≺ on terms such that every R k is ≺-well-founded, and the set-theoretic limit of {R k : κ ε ω} exists, then {R k : κ ε ω} has the well limit behavior; and if (1) there is a well-founded ordering ≺ on terms such that every R k is ≺-well-founded, (2) there is a distance d on terms which is closed under substitutions and contexts and (3) {R k : k ε ω} is Cauchy under d then {R κ: κ ε ω} has the well limit behavior. The results are used to approximate the least Herbrand models of infinite Horn logic programs and real Horn logic programs, and the solutions and Gröbner bases of (infinite) sets of real polynomials by sequences of (finite) sets of rational polynomials.