Two programs are observationally congruent, if and only if they exhibit the same observational behavior in every context they can be placed in. A semantics is compositional if semantical equality implies observational congruence, and fully abstract if semantical equivalence coincides with observational congruence. The compositionality and full abstraction properties for different notions of semantical equivalence ( subsumption equivalence, logical equivalence, and minimal Herbrand model equivalence ) and different operators in an algebra (union, closure, overriding union)
are considered in (Bugliesi et al. 1994). It is worth noting that minimal Herbrand model equivalence coincides with the weak equivalence relation for positive logic programs. As to be defined in Section 3.3, two logic programs are weakly equivalent if and only if they have exactly the same answer sets. As the equivalence based on minimal Herbrand model semantics is not compositional with respect to program union (Bugliesi et al. 1994), we note that it is not a suitable composition operator for our purposes unless further constraints are introduced.

## 2.1 Modularity In Answer Set Programming

There are a number of approaches within answer set programming involving modularity in some sense, but only a few of them really describe a flexible module architecture with a clearly defined interface for module interaction.

Eiter, Gottlob, and Veith (1997) address modularity in ASP in the programmingin-the-small sense. They view program modules as generalized quantifiers as introduced in (Mostowski 1957). The definitions of quantifiers are allowed to nest, that is, program P can refer to another module Q by using it as a generalized quantifier.

The main program is clearly distinguished from subprograms, and it is possible to nest calls to submodules if the so-called call graph is hierarchical, that is, acyclic. Nesting, however, increases the computational complexity depending on the depth of nesting.

Ianni et al. (2004) propose another programming-in-the-small approach to ASP
based on templates. The semantics of programs containing template atoms is determined by an explosion algorithm, which basically replaces the template with a standard logic program. However, the explosion algorithm is not guaranteed to terminate if template definitions are used recursively.

Tari et al. (2005) extend the language of normal logic programs by introducing the concept of import rules for their ASP program modules. There are three types of import rules which are used to import a set of tuples X for a predicate q from another module. An ASP module is defined as a quadruple of a module name, a set of parameters, a collection of normal rules and a collection of import rules. Semantics is only defined for modular programs with acyclic dependency graph, and answer sets of a module are defined with respect to the modular ASP program containing it. Also, it is required that import rules referring to the same module always have the same form.

Programming-in-the-large approaches in ASP are mostly based on Lifschitz and Turner's splitting-set theorem (Lifschitz and Turner 1994) or are variants ofit. The class of logic programs considered in (Lifschitz and Turner 1994) is that of extended 5