Fairness in Theorem Proving

Опубликовано 27 июля 2016, 19:31

Fairness is a fundamental concept that arises in many aspects of computing. In theorem proving a refutationally complete inference system is complemented with a fair search plan, or strategy, to obtain a complete theorem-proving method. Although in practice we often give up on completeness, we usually do so by deliberately weakening a complete method, so that the practical interest in incomplete methods does not diminish the importance of fairness. While many refutationally complete non-trivial inference systems are known, the design of fair search plans that are not trivial and unfair search plans that are useful is a challenge. In this talk we discuss various notions of fairness for different theorem-proving paradigms. We analyze the connection between fairness and redundancy, how both are defined in terms of orderings, how these can be formula orderings or proof orderings. The latter allow us to distinguish between fairness, which yields completeness, and uniform fairness, which yields saturation, suggesting that saturation is too strong for theorem proving.