Abstract
In the context of logic program updates, a knowledge base, which is presented as a logic program, can be updated in terms of another logic program, i.e. a set of update rules. In this paper, we investigate the complexity of logic program updates where conflict resolution on defeasible information is explicitly taken into account in an update. We show that in general the problem of model checking in logic program updates is co-NP-complete, and the corresponding inference problem is ΠP 2 -complete. We also characterize particular classes of update specifications where the inference problem has a lower computational complexity. These results confirm that logic program update, even if with the issue of conflict resolution on defeasible information to be presented, is not harder than the principal update tasks.
| Original language | English |
|---|---|
| Title of host publication | AI 2001 |
| Subtitle of host publication | Advances in Artificial Intelligence - 14th Australian Joint Conference on Artificial Intelligence, Proceedings |
| Editors | Markus Stumptner, Dan Corbett, Mike Brooks, Dan Corbett |
| Publisher | Springer Verlag |
| Pages | 631-642 |
| Number of pages | 12 |
| ISBN (Print) | 9783540429609 |
| DOIs | |
| Publication status | Published - 2001 |
| Event | 14th Australian Joint Conference on Artificial Intelligence, AI 2001 - Adelaide, Australia Duration: 10 Dec 2001 → 14 Dec 2001 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2256 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 14th Australian Joint Conference on Artificial Intelligence, AI 2001 |
|---|---|
| Country/Territory | Australia |
| City | Adelaide |
| Period | 10/12/01 → 14/12/01 |
Bibliographical note
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2001.