Abstractibvbon Within Partial Deduction for Linear Logic

摘要

Abstraction has been used extensively in Artificial Intelligence (AI) planning, human problem solving and theorem proving. In this article we show how to apply abstraction within Partial Deduction (PD) formalism for Linear Logic (LL). The proposal is accompanied with formal results identifying limitations and advantages of the approach. We adapt a technique from AI planning for constructing abstraction hierarchies, which are then exploited during PD. Although the complexity of PD for propositional LL is generally decidable, by applying abstraction the complexity is reduced to polynomial in certain cases.