Strategies on functional languages

点击翻译按钮获取中文摘要

This research is toward removing gaps that prevent from applying results of term rewriting systems (TRSs for short) to factional languages. The following results were obtained ;(1) Only TRSs having few rules can be decided whether they are NV-sequential in realistic execution time. The execution time of the calculating an index of a given term and a TRS is similar to the decision problem.(2) We extended the notion of root indexes of TRSs to TRSs with priorities and construct a prototype system that efficiently caliculate indexes for head normal forms of strongly sequential priority TRSs.(3) The strategy that reduce needed redex is normalizing.(4) We showd a class of higher-order TRSs in which the dependency pair method, a mecanized proof technique of termination, is effective.(5) The leftmost innermost reduction strategy is normalizing for terminating, right-linear and root over-lapping TRSs.