An Application of Proof-Theory in Answer Set Programming

Free registration required

Executive Summary

The use of proof theory in logic based formalisms for constraint solving is pervasive. For example, in Satisfiability (SAT), proof theoretic methods are used to find lower bounds on complexity of various SAT algorithms. However, proof-theoretic methods have not played as prominent role in Answer Set Programming (ASP) formalisms. This is not to say that there were no attempts to apply proof-theoretic methods in ASP. To give a few examples, Marek and Truszczynski in [MT93] used the proof-theoretic methods to characterize Reiter's extensions in Default Logic (and thus stable semantics of logic programs). Bonatti [Bo04] and separately Milnikel [Mi05] devised non-monotonic proof systems to study skeptical consequences of programs and default theories.

  • Format: PDF
  • Size: 150.31 KB