Hyperequivalence of logic programs with respect to supported models

Mirosław Truszczyński, Stefan Woltran

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 languageEnglish
Pages (from-to)331-365
Number of pages35
JournalAnnals of Mathematics and Artificial Intelligence
Issue number1-4
StatePublished - 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.


  • Hyperequivalence
  • Logic programs
  • Supported models

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Hyperequivalence of logic programs with respect to supported models'. Together they form a unique fingerprint.

Cite this