Compact Representations of Revision of Horn Clauses

Paolo Liberatore

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 [Delta]p2 to [Delta]p3 in 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},
 }
 
HTTP download.
FTP download.