Characterising approximate problem-solving
by partial pre- and postconditions.

Frank van Harmelen
Annette ten Teije

In Software Engineering, the functionality of a program is traditionally characterised by pre- and postconditions: if the preconditions are fulfilled then the postconditions are guaranteed to hold, but if the preconditions are not fulfilled, no postconditions are guaranteed at all. In this paper, we study how the functionality of a program is affected when the preconditions are only partially fulfilled. This is particularly important for AI methods which employ heuristics. For such heuristics it is typically not possible to exactly characterise the preconditions under which they function optimally. Furthermore, they still function reasonably well (although perhaps suboptimally) under less then ideal preconditions. As a result, the classical pre- postcondition approach does not suffice to characterise such heuristic methods. We introduce a framework in which we are able to characterise partially fulfilled pre- and postconditions, and their relation to each other. We also present the proof obligations that must be met when using programs under partially fulfilled preconditions. We show that the classical characterisation of programs can be seen as a special case of our gradual characterisation. We illustrate our framework with two simple diagnostic algorithms which coincide in the classical approach, but which turn out to behave differently under gradually relaxed preconditions.

(PDF paper, 78Kb) 

@InProceedings{ECAI98,
  author =       "F. van Harmelen and A. ten Teije",
  title =        "Characterising approximate problem-solving
                  by partial pre- and postconditions",
  booktitle =    "Proceedings of {ECAI}'98",
  year =         1998,
  pages =        "78--82",
  address =      "Brighton",
  month =        "August",
  keywords = {Approximate Reasoning},
  urlPaper = "http://www.cs.vu.nl/~frankh/postscript/ECAI98.pdf"
}
Copyright © Wiley 1998

<- Back to list of papers