Relativized hyperequivalence of logic programs for modular programming

Mirosaw Truszczyski, Stefan Woltran

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


A recent framework of relativized hyperequivalence of programs offers a unifying generalization of strong and uniform equivalence. It seems to be especially well suited for applications in program optimization and modular programming due to its flexibility that allows us to restrict, independently of each other, the head and body alphabets in context programs. We study relativized hyperequivalence for the three semantics of logic programs given by stable, supported, and supported minimal models. For each semantics, we identify four types of contexts, depending on whether the head and body alphabets are given directly or as the complement of a given set. Hyperequivalence relative to contexts where the head and body alphabets are specified directly has been studied before. In this paper, we establish the complexity of deciding relativized hyperequivalence with respect to the three other types of context programs.

Original languageEnglish
Pages (from-to)781-819
Number of pages39
JournalTheory and Practice of Logic Programming
Issue number6
StatePublished - Nov 2009

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 and P20704.


  • Answer-set programming
  • Complexity
  • Minimal models
  • Relativized equivalence
  • Stable models
  • Strong equivalence
  • Supported models
  • Uniform equivalence

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Artificial Intelligence


Dive into the research topics of 'Relativized hyperequivalence of logic programs for modular programming'. Together they form a unique fingerprint.

Cite this