Computing More Specific Versions of Conditional Rewriting Systems

Abstract Rewrite systems obtained by some automated transformation often have a poor syntactic structure even if they have good properties from a semantic point of view. For instance, a rewrite system might have overlapping left-hand sides even if it can only produce at most one constructor normal form (i. e. , value). In this paper, we propose a method for computing “more specific” versions of deterministic conditional rewrite systems (i. e. , typical functional programs) by replacing a given rule (e. g. , an overlapping rule) with a finite set of instances of this rule. In some cases, the technique is able to produce a non-overlapping system from an overlapping one. We have applied the transformation to improve the systems produced by a previous technique for function inversion with encouraging results (all the overlapping systems were successfully transformed to non-overlapping systems).

Authors

• Naoki Nishida 0001
• Germán Vidal

Keywords

No keywords are indexed for this paper.