Abstract
Recent research in nonmonotonic logic programming has focused on certain types of program equivalence, which we refer to here as hyperequivalence, that are relevant for program optimization and modular programming. So far, most results concern hyperequivalence relative to the stable-model semantics. However, other semantics for logic programs are also of interest, especially the semantics of supported models which, when properly generalized, is closely related to the autoepistemic logic of Moore. In this paper, we consider a family of hyperequivalence relations for programs based on the semantics of supported and supported minimal models. We characterize these relations in model-theoretic terms. We use the characterizations to derive complexity results concerning testing whether two programs are hyperequivalent relative to supported and supported minimal models.
| Original language | English |
|---|---|
| Pages (from-to) | 331-365 |
| Number of pages | 35 |
| Journal | Annals of Mathematics and Artificial Intelligence |
| Volume | 53 |
| Issue number | 1-4 |
| DOIs | |
| State | Published - Aug 2008 |
Bibliographical note
Funding Information:This work was partially supported by the NSF grant IIS-0325063, the KSEF grant KSEF-1036-RDE-008, and by the Austrian Science Fund (FWF) under grants P18019-N04 and P20704-N18.
Funding
This work was partially supported by the NSF grant IIS-0325063, the KSEF grant KSEF-1036-RDE-008, and by the Austrian Science Fund (FWF) under grants P18019-N04 and P20704-N18.
| Funders | Funder number |
|---|---|
| National Science Foundation Arctic Social Science Program | IIS-0325063, KSEF-1036-RDE-008 |
| Austrian Science Fund/FWF | P18019-N04, P20704-N18 |
Keywords
- Hyperequivalence
- Logic programs
- Supported models
ASJC Scopus subject areas
- Artificial Intelligence
- Applied Mathematics