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)

Abstract

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 publicationAAAI Spring Symposium - Technical Report
Pages2-8
Number of pages7
VolumeSS-11-06
Publication statusPublished - 2011
Externally publishedYes
Event2011 AAAI Spring Symposium - Stanford, CA, United States
Duration: Mar 21 2011Mar 23 2011

Other

Other2011 AAAI Spring Symposium
CountryUnited States
CityStanford, CA
Period3/21/113/23/11

Fingerprint

Knowledge representation

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this

Adaricheva, K., Sloan, R. H., Szörényi, B., & Turán, G. (2011). Horn belief contraction: Remainders, envelopes and complexity. In AAAI Spring Symposium - Technical Report (Vol. SS-11-06, pp. 2-8)

Horn belief contraction : Remainders, envelopes and complexity. / Adaricheva, Kira; Sloan, Robert H.; Szörényi, Balázs; Turán, György.

AAAI Spring Symposium - Technical Report. Vol. SS-11-06 2011. p. 2-8.

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

Adaricheva, K, Sloan, RH, Szörényi, B & Turán, G 2011, Horn belief contraction: Remainders, envelopes and complexity. in AAAI Spring Symposium - Technical Report. vol. SS-11-06, pp. 2-8, 2011 AAAI Spring Symposium, Stanford, CA, United States, 3/21/11.
Adaricheva K, Sloan RH, Szörényi B, Turán G. Horn belief contraction: Remainders, envelopes and complexity. In AAAI Spring Symposium - Technical Report. Vol. SS-11-06. 2011. p. 2-8
Adaricheva, Kira ; Sloan, Robert H. ; Szörényi, Balázs ; Turán, György. / Horn belief contraction : Remainders, envelopes and complexity. AAAI Spring Symposium - Technical Report. Vol. SS-11-06 2011. pp. 2-8
@inproceedings{5dc38047648547f6882508dcc3dd3e83,
title = "Horn belief contraction: Remainders, envelopes and complexity",
abstract = "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.",
author = "Kira Adaricheva and Sloan, {Robert H.} and Bal{\'a}zs Sz{\"o}r{\'e}nyi and Gy{\"o}rgy Tur{\'a}n",
year = "2011",
language = "English",
isbn = "9781577354987",
volume = "SS-11-06",
pages = "2--8",
booktitle = "AAAI Spring Symposium - Technical Report",

}

TY - GEN

T1 - Horn belief contraction

T2 - Remainders, envelopes and complexity

AU - Adaricheva, Kira

AU - Sloan, Robert H.

AU - Szörényi, Balázs

AU - Turán, György

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80051490670&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80051490670&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:80051490670

SN - 9781577354987

VL - SS-11-06

SP - 2

EP - 8

BT - AAAI Spring Symposium - Technical Report

ER -