Horn belief contraction: Remainders, envelopes and complexity

Kira Adaricheva, Robert H. Sloan, Balázs Szörényi, György Turán

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


A recent direction within belief revision theory is to develop a theory of belief change for the Horn knowledge representation framework. We consider questions related to the complexity aspects of previous work, leading to questions about Horn envelopes (or Horn LUB's), introduced earlier in the context of knowledge compilation. A characterization is obtained of the remainders of a Horn belief set with respect to a consequence to be contracted, as the Horn envelopes of the belief set and an elementary conjunction corresponding to a truth assignment satisfying a certain body building formula. This gives an efficient algorithm to generate all remainders, each represented by a truth assignment. On the negative side, examples are given of Horn belief sets and consequences where Horn formulas representing the result of most contraction operators, based either on remainders or on weak remainders, must have exponential size.

Original languageEnglish
Title of host publicationLogical Formalizations of Commonsense Reasoning - Papers from the AAAI Spring Symposium, Technical Report
Number of pages7
Publication statusPublished - Aug 15 2011
Event2011 AAAI Spring Symposium - Stanford, CA, United States
Duration: Mar 21 2011Mar 23 2011

Publication series

NameAAAI Spring Symposium - Technical Report


Other2011 AAAI Spring Symposium
CountryUnited States
CityStanford, CA

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Horn belief contraction: Remainders, envelopes and complexity'. Together they form a unique fingerprint.

Cite this