On the complexity of extension checking in default logic

Paolo Liberatore

Information Processing Letters

The complexity of deciding equivalence of a formula to an extension of a default theory is investigated for the Reiter, justified, constrained, and rational semantics.


 @article{libe-06-c,
 title = {On the complexity of extension checking in default
 logic},
 year = {2006},
 author = {Liberatore, Paolo},
 journal = {Information Processing Letters},
 pages = {61--65},
 number = {2},
 volume = {98},
 }
 
doi: 10.1016/j.ipl.2005.12.005