| Home > Publications > Reports > Informatics (CW) |
CW 248
M. Leuschel, B. Martens and D. De Schreye
Controlling generalisation and polyvariance in partial deduction of normal logic programs
Abstract
In this paper, we further elaborate global control for partial deduction: For which atoms, among possibly infinitely many, should partial deductions be produced, meanwhile guaranteeing correctness as well as termination, and providing ample opportunities for finegrained polyvariance? Our solution is based on two ingredients. First, we use the well-known concept of a characteristic tree to guide abstraction (or generalisation) and polyvariance, and aim for producing one speicialised procedure per characteristic tree generated. Previous work along this line failed to provide abstraction correctly dealing with characteristic trees. We show how this can be rectified in an elegant way. Secondly, we structure combinations of atoms and associated characteristic trees in global trees registering ``causal'' relationships among such pairs. This will allow us to spot looming non-termination and consequently perform proper gneralisation in order to avert the danger, without having to impose a depth bound on characteristic trees. Leaving unspecified the specific local control one may wish to plug in, the resulting global control strategy enables partial deduction that always terminates in an elegant, non ad hoc way, while providing excellent specialisation as well as fine-grained (but reasonable) polyvariance.
report.pdf / mailto: M. Leuschel