, a)}), m) + ) (since GR and Cn are increasing when the program increases, m) + ) = Cn(GR(P ? Q ?Y, m) + ) = m and ?Y = Y \ { f act(a)} ? Y such that P ?Y ? Q is consistent

X. Let, Q. )-;-p-?-q-?-x), P. Each-x-?-x, and . ?-x-?-;-p-?-q-?-x-;-x-?-ca, By Definition 10, P ? X ? Q is consistent, that is, ?m ? AS, We have to show: (1) m ? Mod(P ? Q)

, By Theorem 1, since m ? AS(P ? Q ? X), m ? Mod(P ? Q)

. P-?-q-?-x), P. For-each-x-?-x, Q. , ). Ca-;-p, and Q. , Now, by hypothesis, m ? AS

X. P-?-q-?-x-and-if-x-?-x, Q. ). Therefore-x-=-x, and X. Min, So m is an answer set of, Q) then ?m s.t. X ? Nded(m , P ? Q) and m ? AS(P ? Q ? X )

, This means that |R ? Y | is not minimal, and consequently the number of atoms is(x) ? X 0 will be larger than the number of atoms is(x) ? X. If X O ? AS((P\R 0 )?Y 0 ?Q), then X 0 corresponds to an independent set S 0 such that |S 0 | > |P|?(k RY /2), because none of the constraints in Q 2 are satisfied

, ? If we do not find such a triplet, this means that there is no independent set which is larger than k = |P| ? (k RY /2), and then

Y. , R. , Q. , R. , and Q. , We now show that G contains a maximum independent set S of size k only if the set of atoms X = ?(S) is such that there exist a set of facts Y and a set of rules R

G. and Q. )-;-p-\-r)-?-y-?-q), We prove that S is a maximal independent set of size k = |V | ? (k RY /2). Let us compute ((P \ R) ?Y ? Q) ?(S)

?. ,

, ? {? body + (r) | r ? Q 6 , is 2 (x) ? body ? (r)

, ? {? body + (r) | r ? Q 6 , is 1 (x) ? body ? (r)

, ? All rules in P \ R. Note that, as ?(S) ? AS((P \ R) ?Y ? Q), these rules are such that is 1 (x) ? ?(S), and thus x ? S

. P-\-r)-?-y-?-q, ? all rules in Y , whose content is Y = {(is 2 (x).) | is 2 (x) ? ?(S)}, because ?(S) ? AS

. P-\-r)-?-y-?-q,

. P-\-r)-?y-?-q, e(x, y).) ? Q 2 which would prohibit ?(S) to be an answer set of (P \ R) ?Y ? Q. Similarly, ?(is 2 (x), is 2 (y)) ? ?(S) 2 , there is no fact (e(x, y).) ? Q 1 because if it was the case, ? Q 1 because if it was the case, there would exist a constraint (? is 1 (x), is 1 (y)

?. E. |v-|-?-|y-|-=-|p-\-r|, Thus S is an independent set of size k

(. Moreover, R. , and Q. , there is no (Y 0 , R 0 ), with R 0 ? P, atom(Y 0 ) ? atom(P ? Q)

, ? for any such set Y 0 there exists a pair of rules (is 2 (x) ? not is 2 (x)., is 2 (y) ? not is 2 (y))

, ).) ? Q, which means in turn that {x | is 2 (x) ? Y 0 } is not an independent set of G, or, References Alchourrón, Studia Logica, vol.44, issue.4, pp.14-37, 1985.

J. Alferes, J. Leite, L. Pereira, H. Przymusinska, and T. Przymusinski, Dynamic updates of non-monotonic knowledge bases, Journal of Logic Programming, vol.45, issue.1-3, pp.43-70, 2000.

C. Baral, Knowledge Representation, Reasoning and Declarative Problem Solving, 2003.

K. Bauters, S. Schockaert, M. D. Cock, and D. Vermeir, Characterizing and extending answer set semantics using possibility theory. Theory and Practice of Logic Programming, vol.15, pp.79-116, 2015.

S. Benferhat, J. Bennaim, O. Papini, and E. Würbel, Answer set programming encoding of prioritized removed sets revision: Application to GIS, Applied Intelligence, vol.32, pp.60-87, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00869357

S. Benferhat, C. Cayrol, D. Dubois, J. Lang, and H. Prade, Inconsistency management and prioritized syntax-based entailment, Proceedings of the 13 th International Joint Conference on Artificial Intelligence (IJCAI'93), pp.640-645, 1993.

S. Benferhat, D. Dubois, and H. Prade, How to infer from inconsisent beliefs without revising, Proceedings of the 14 th International Joint Conference on Artificial Intelligence (IJCAI'95), pp.1449-1457, 1995.

S. Binnewies, Z. Zhuang, and K. Wang, Partial meet revision and contraction in logic programs, Proceedings of the 29 th AAAI Conference on Artificial Intelligence (AAAI'15), pp.1439-1445, 2015.

J. P. Delgrande, P. Peppas, and S. Woltran, AGM-style belief revision of logic programs under answer set semantics, Proceedings of the 12 th Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13), pp.264-276, 2013.

J. P. Delgrande, T. Schaub, H. Tompits, and S. Woltran, Belief Revision of Logic Programs under Answer Set Semantics, Proceedings of the 11 th International Conference on Principles of Knowledge Representation and Reasoning (KR'08), pp.411-421, 2008.

J. P. Delgrande, T. Schaub, H. Tompits, and S. Woltran, Merging logic programs under answer set semantics, Proceedings of the 25 th International Conference on Logic Programming (ICLP'09), pp.160-174, 2009.

J. P. Delgrande, T. Schaub, H. Tompits, and S. Woltran, A model-theoretic approach to belief change in answer set programming, ACM Transaction on Computational Logic, vol.14, issue.2, pp.1-46, 2013.

T. Eiter, M. Fink, G. Sabbatini, and H. Tompits, On properties of update sequences based on causal rejection. Theory and Practice of Logic Programming, vol.2, pp.711-767, 2002.

L. Garcia, C. Lefèvre, O. Papini, I. Stéphan, and E. Würbel, A semantic characterization for ASP base revision, Proceedings of the 11 th International Conference on Scalable Uncertainty Management (SUM'17), pp.334-347, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01770946

L. Garcia, C. Lefèvre, O. Papini, I. Stéphan, and E. Würbel, Possibilistic asp base revision by certain input, Proceedings of the 27 th International Joint Conference on Artificial Intelligence (IJCAI'18), pp.1824-1830, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01794353

M. Gebser, B. Kaufmann, and T. Schaub, Conflict-driven answer set solving: From theory to practice, Artificial Intelligence, vol.187, pp.52-89, 2012.

M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, Proceedings of the 5 th International Conference on Logic Programming (ICLP'88), pp.1070-1080, 1988.

S. O. Hansson, Semi-revision, Journal of Applied Non-classical Logics, vol.7, pp.151-175, 1997.

S. O. Hansson, A text of belief dynamics theory change and database updating, Applied Logic Series, p.11, 1999.

S. O. Hansson and R. Wassermann, Local change, Studia Logica, vol.70, issue.1, pp.49-76, 2002.

J. Hué, O. Papini, and E. Würbel, Removed Sets Fusion: Performing Off the Shelf, Proceedings of the 18 th European Conference on Artificial Intelligence (ECAI'08), pp.94-98, 2008.

J. Hué, O. Papini, and E. Würbel, Merging belief bases represented by logic programs, Proceedings of the 10 th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU'09), pp.371-382, 2009.

J. Hué, O. Papini, and E. Würbel, Extending belief base change to logic programs with ASP, Trends in Belief Revision and Argumentation Dynamics, 2013.

H. Katsuno and A. Mendelzon, Propositional knowledge base revision and minimal change, Artificial Intelligence, vol.52, issue.3, pp.263-294, 1991.

P. Krümpelmann and G. Kern-isberner, Belief Base Change Operations for Answer Set Programming, Proceedings of the 13 th European Conference on Logics in Artificial Intelligence (JELIA'12), pp.294-306, 2012.

D. Lehmann, Belief revision, revised, Proceedings of the 14 th International Joint Conference on Artificial Intelligence (IJCAI'95), pp.1534-1540, 1995.

N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob et al., The DLV system for knowledge representation and reasoning, ACM Transaction on Computational Logic, vol.7, issue.3, pp.499-562, 2006.

P. Nicolas, L. Garcia, I. Stéphan, and C. Lefèvre, Possibilistic uncertainty handling for answer set programming, Annals of Mathematics and Artificial Intelligence, vol.47, issue.1-2, pp.139-181, 2006.

I. Niemelä, Logic programs with stable model semantics as a constraint programming paradigm, Annals of Mathematics and Artificial Intelligence, vol.25, issue.3-4, pp.241-273, 1999.

C. H. Papadimitriou, Computational Complexity, chap, vol.17, p.412, 1994.

O. Papini, A Complete Revision Function in Propositional Calculus, Proceedings of the 10 th European Conference on Artificial Intelligence (ECAI'92), pp.339-343, 1992.

R. Reiter, A logic for default reasoning, Artificial Intelligence, vol.13, issue.1-2, pp.81-132, 1980.

C. Sakama and K. Inoue, Updating Extended Logic Programs through Abduction, Proceedings of the 5 th Conference on Logic Programming and Nonmonotonic Reasoning (LP-NMR'99), pp.147-161, 1999.

T. Schaub and S. Woltran, Answer set programming unleashed!. KI, vol.32, pp.105-108, 2018.

N. Schwind and K. Inoue, Characterization of logic program revision as an extension of propositional revision. Theory and Practice of Logic Programming, vol.16, pp.111-138, 2016.

M. Slota and J. Leite, On Semantic Update Operators for Answer-Set Programs, Proceedings of the 19 th European Conference on Artificial Intelligence (ECAI'10), pp.957-962, 2010.

M. Slota and J. Leite, The rise and fall of semantic rule updates based on se-models. Theory and Practice of Logic Programming, vol.14, pp.869-907, 2014.

H. Turner, Strong equivalence made easy: nested expressions and weight constraints, Theory and Practice of Logic Programming, vol.3, pp.609-622, 2003.

E. Würbel, R. Jeansoulin, and O. Papini, Revision : An application in the framework of GIS, Proceedings of the 7 th International Conference on Principles of Knowledge Representation and Reasoning (KR'00), pp.505-518, 2000.

Y. Zhang and N. Y. Foo, Updating Logic Programs, Proceedings of the 13 th European Conference on Artificial Intelligence (ECAI'98), pp.403-407, 1998.

Z. Zhuang, J. Delgrande, A. Nayak, and A. Sattar, A New Approach for Revising Logic Programs, Proceedings of the 16 th International Workshop on Non-Monotonic Reasoning (NMR'16), pp.171-176, 2016.

Z. Zhuang, J. Delgrande, A. Nayak, and A. Sattar, Reconsidering AGM-style belief revision in the context of logic programs, Proceedings of the 22 th European Conference on Artificial Intelligence (ECAI'16), pp.671-679, 2016.