, 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
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)
, Now, by hypothesis, m ? AS
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
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 ,
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
, ? all rules in Y , whose content is Y = {(is 2 (x).) | is 2 (x) ? ?(S)}, because ?(S) ? AS
,
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) ,
Thus S is an independent set of size k ,
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.
Dynamic updates of non-monotonic knowledge bases, Journal of Logic Programming, vol.45, issue.1-3, pp.43-70, 2000. ,
Knowledge Representation, Reasoning and Declarative Problem Solving, 2003. ,
Characterizing and extending answer set semantics using possibility theory. Theory and Practice of Logic Programming, vol.15, pp.79-116, 2015. ,
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
Inconsistency management and prioritized syntax-based entailment, Proceedings of the 13 th International Joint Conference on Artificial Intelligence (IJCAI'93), pp.640-645, 1993. ,
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. ,
Partial meet revision and contraction in logic programs, Proceedings of the 29 th AAAI Conference on Artificial Intelligence (AAAI'15), pp.1439-1445, 2015. ,
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. ,
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. ,
Merging logic programs under answer set semantics, Proceedings of the 25 th International Conference on Logic Programming (ICLP'09), pp.160-174, 2009. ,
A model-theoretic approach to belief change in answer set programming, ACM Transaction on Computational Logic, vol.14, issue.2, pp.1-46, 2013. ,
On properties of update sequences based on causal rejection. Theory and Practice of Logic Programming, vol.2, pp.711-767, 2002. ,
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
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
Conflict-driven answer set solving: From theory to practice, Artificial Intelligence, vol.187, pp.52-89, 2012. ,
The stable model semantics for logic programming, Proceedings of the 5 th International Conference on Logic Programming (ICLP'88), pp.1070-1080, 1988. ,
Semi-revision, Journal of Applied Non-classical Logics, vol.7, pp.151-175, 1997. ,
A text of belief dynamics theory change and database updating, Applied Logic Series, p.11, 1999. ,
Local change, Studia Logica, vol.70, issue.1, pp.49-76, 2002. ,
Removed Sets Fusion: Performing Off the Shelf, Proceedings of the 18 th European Conference on Artificial Intelligence (ECAI'08), pp.94-98, 2008. ,
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. ,
Extending belief base change to logic programs with ASP, Trends in Belief Revision and Argumentation Dynamics, 2013. ,
Propositional knowledge base revision and minimal change, Artificial Intelligence, vol.52, issue.3, pp.263-294, 1991. ,
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. ,
Belief revision, revised, Proceedings of the 14 th International Joint Conference on Artificial Intelligence (IJCAI'95), pp.1534-1540, 1995. ,
The DLV system for knowledge representation and reasoning, ACM Transaction on Computational Logic, vol.7, issue.3, pp.499-562, 2006. ,
Possibilistic uncertainty handling for answer set programming, Annals of Mathematics and Artificial Intelligence, vol.47, issue.1-2, pp.139-181, 2006. ,
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. ,
Computational Complexity, chap, vol.17, p.412, 1994. ,
A Complete Revision Function in Propositional Calculus, Proceedings of the 10 th European Conference on Artificial Intelligence (ECAI'92), pp.339-343, 1992. ,
A logic for default reasoning, Artificial Intelligence, vol.13, issue.1-2, pp.81-132, 1980. ,
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. ,
Answer set programming unleashed!. KI, vol.32, pp.105-108, 2018. ,
Characterization of logic program revision as an extension of propositional revision. Theory and Practice of Logic Programming, vol.16, pp.111-138, 2016. ,
On Semantic Update Operators for Answer-Set Programs, Proceedings of the 19 th European Conference on Artificial Intelligence (ECAI'10), pp.957-962, 2010. ,
The rise and fall of semantic rule updates based on se-models. Theory and Practice of Logic Programming, vol.14, pp.869-907, 2014. ,
Strong equivalence made easy: nested expressions and weight constraints, Theory and Practice of Logic Programming, vol.3, pp.609-622, 2003. ,
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. ,
Updating Logic Programs, Proceedings of the 13 th European Conference on Artificial Intelligence (ECAI'98), pp.403-407, 1998. ,
A New Approach for Revising Logic Programs, Proceedings of the 16 th International Workshop on Non-Monotonic Reasoning (NMR'16), pp.171-176, 2016. ,
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. ,