welcome: please sign in
location: ProblemsDescription / MultiContextSystemQuerying

Multi-Context System Querying

Problem Description

We consider queries over Multi-Context Systems (MCSs), which are a formalism for interlinking distributed (possibly nonmonotonic) knowledge bases - here called contexts - using pointwise information exchange in the form of (possibly nonmonotonic) logic programming rules - here called bridge rules. The "Equilibrium Semantics" definition which is the subject of these benchmark instances was introduced by Brewka and Eiter [1]. Intuitively, these semantics provide a logic programming layer that links contexts without imposing a foundedness condition on that knowledge integration layer. We consider systems where each context C_i is a propositional logic program P_i under stable model semantics.

A query to output atom in(ContextID,Atom) shall return true iff in all equilibria of the encoded MCS, the atom "Atom" is contained in the stable model of context "ContextID".

Rationale for this kind of benchmark instances: The problem instances consist of subprograms (contexts) that are interacting in a not very tight way (via bridge rules). The reasoning task itself is not hard, but instance sizes could become a challenge.

A more detailed MCS semantics definition follows. (Note that the benchmark instance is for the system competition, so the semantics are taken care of in the given encoding.) For an MCS with n contexts, a belief state S is an n-tuple of models, one model S_i for each context C_i. A bridge rule of the form

is applicable in belief state S if p_i \in S_{c_i},..., p_j \notin S_{c_j},... . Now S is an equilibrium if each program P_i plus heads bridge rules that are applicable wrt S has S_i as a stable model. For details on the semantics definition [1] and work leading up to that definition [2,3] please refer to references given below.

Input format

Input Predicates: ctx/1, ctxrule/2, ctxrulehead/2, ctxrulebody/3, brule/2, brulehead/2, brulebody/4

Input predicates specify contexts and bridge rules as follows:

Output format

Output Predicates: in/2

Example

Author(s)

Author: Peter Schüller
Affiliation: Institute of Information Systems, TU Vienna

References

ASP Competition 2011: ProblemsDescription/MultiContextSystemQuerying (last edited 2011-01-10 10:17:29 by CarmenSantoro)