A Generalized Normalizing Strategy
Riad Jabri · Dirāsāt. Al-ʿulūm al-asāsiyyaẗ · 2010
Terms rewriting systems (TRS) has an important modeling role in many aspects of computing systems. However, there is a need for efficient, safe and terminating reductions of such systems. Hence, the normalization and the reductions of TRS have gained an increasing attention from a theoretical as well as from a practical point of view. In this work, we have formalized a generic normalization strategy, based on proposed functional concepts for TRS. Two frameworks, called GNFR1 and GNFR2, have been proposed for implementing such strategy. The computational results of GNFR1 and GNFR2 have been compared to the publicly available results of similar approaches. They have demonstrated their correctness and generality, in addition to their superiority in terms of reducing the cardinality of the rewriting sequences and the number of the terminating reductions. Furthermore, based on proposed functional concepts for positional matching and its aggregation into terms matching, the proposed frameworks can be applied to other than the constructor-based TRS and according to different reducing strategies.