Compact Representations of Revision of Horn Clauses

Proceedings of the Eighth Australian Joint Artificial Intelligence Conference (AI'95)

Several methods are proposed, in the past years, to attempt to define how to deal with a dynamic knowledge. From a computational point of view, different definitions lead to different different computational property, namely to a complexity between DELTAp2to DELTAp3in the polynomial hierarchy. Restricting the analysis to cases in which some operations becomes tractable (Horn case), other problems arises. We show that, providing some assumption on the polynomial hierarchy, many update operators are uncompactable, i.e. it is impossible to find a representation of the result without an exponential-size explosion. We supply also the explicit representations of the updates for which it is possible.

 @inproceedings{libe-95,
 title = {Compact Representations of Revision of Horn Clauses},
 year = {1995},
 author = {Liberatore, Paolo},
 booktitle = {Proceedings of the Eighth Australian Joint Artificial Intelligence
 Conference (AI'95)},
 pages = {347-354},
 }