  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.
  To appear in Theory and Practice of Logic Programming (TPLP).
