Eliminating Selectors from Term Rewriting Systems(Theory of Rewriting Systems and Its Applications)
Yutaka Kikuchi · Institutional Repositories DataBase (IRDB) · 1995
Function symbols of term rewriting systems (TRSs) can be classified into three categories, namely, constructors, selectors, and defined operators in terms of functional programming.The selectors are for convenience of programming and efficient execution of programs, so the constructors and the defined operators are sufficient to construct data structures and to manipulate them.We give a transformation method to eliminate selectors from a TRS.We also introduce a new model of TRSs from the viewpoint of functional programming, and show that an original TRS and the transformed TRS have the almost same model except trivial differences.The transformation method preserves strong termination property.Although the methods do not preserve weak terminating and confluency, we turn out sufficient conditions to keep those properties.