Abstract:
Simplifying assumptions are a powerful technique for dealing with complexity, which is used in all branches of science and engineering. This work develops a formal account of this technique in the context of heuristic search and automated reasoning. We also present a methodology for choosing appropriate simplifying assumptions in specific domains, and demonstrate the use of this methodology with an example of reasoning about typed partial functions in an automated programming assistant.