=Paper=
{{Paper
|id=Vol-1868/p1
|storemode=property
|title=Multi-Context Systems: Dynamics and Evolution
|pdfUrl=https://ceur-ws.org/Vol-1868/p1.pdf
|volume=Vol-1868
|authors=Pedro Cabalar,Stefania Costantini,Andrea Formisano
|dblpUrl=https://dblp.org/rec/conf/lpnmr/CabalarCF17
}}
==Multi-Context Systems: Dynamics and Evolution==
https://ceur-ws.org/Vol-1868/p1.pdf
Multi-Context Systems: Dynamics and Evolution?
Pedro Cabalar, Stefania Costantini, and Andrea Formisano
1
University of Corunna, Spain, email: cabalar@udc.es
2
Università di L’Aquila, Italy, email: stefania.costantini@univaq.it
3
Università di Perugia, Italy, email: andrea.formisano@unipg.it
Abstract. Multi-Context Systems (MCS) model, using Computational Logic,
distributed systems composed of heterogeneous sources, or “contexts”, interact-
ing via special rules called “bridge rules”. In this paper, we consider how to en-
hance flexibility and generality in bridge-rules definition and application.
1 Introduction
Multi-Context Systems (MCSs) have been proposed in Artificial Intelligence and
Knowledge Representation to model information exchange among heterogeneous
sources [3, 4, 6]. MCSs do not make any assumption about such sources nor require
them to be homogeneous; rather, the MCS approach deals explicitly with their different
representation languages and semantics. These sources, also called contexts or modules,
interact through special interconnection expressions called bridge rules; such rules are
very similar in syntax and in meaning to Datalog or Answer Set Programming (ASP)
rules, save that atoms in their bodies refer to knowledge items to be obtained from ex-
ternal contexts. So, a literal (cj : p) (where p is an atom) in the body of a bridge rule
occurring in context ci means that p can be proved in context cj (given cj ’s underly-
ing logic and semantics and given cj ’s knowledge base present contents), vice versa
not (cj : p) means p cannot be proved in cj . In case the entire body “succeeds” then the
bridge rule can be applied, and its conclusion can be exploited within context ci .
The reason why MCSs are particularly interesting is that they aim at a formal mod-
eling of real applications requiring access to distributed sources, possibly on the web.
In many application domains the adoption of MCSs can bring real advances, when-
ever different types of heterogeneous information systems are involved and a rigorous
formalization should be adopted, also in view of reliability and verifiability of the result-
ing systems. Notice that this kind of systems often involve agents; MCSs encompassing
logical agents have in fact been proposed in [8].
Given the potential impact of MCSs for practical knowledge representation and rea-
soning, there are some aspects in which their definition is still too abstract. In this paper,
we introduce and discuss some formal extensions of MCSs, useful for a practical use
in dynamic environments, and we try to provide guidelines for implementations. The
?
This work is partially supported by INdAM-GNCS-17 project, by Xunta de Galicia, Spain
(projects GPC ED431B 2016/035 and 2016-2019 ED431G/01 for CITIC center) and by the
European Regional Development Fund (ERDF).
paper considers the following aspects. (i) The specification of proactive bridge-rule ac-
tivation, i.e., a bridge-rule in our approach is no longer applied whenever applicable,
but it must be explicitly enabled by the context where it occurs. (ii) The explicit defi-
nition of evolution of an MCS over time in consequences of updates that can be more
general than sensor input as treated in [6]. (iii) A specification of bridge-rule grounding
in an evolving MCS. (iv) The definition of practical modalities of execution of bridge
rules in a distributed MCS. (v) Bridge rules patterns, by which we make bridge rules
parametric w.r.t. contexts by introducing special terms called context designators to be
replaced by actual context names; this is in our opinion a very important extension,
which allows general bridge rules schemata to be specialized to actual bridge rules by
choosing which specific contexts (of a certain kind) should specifically be queried in
the situation at hand. There is a relation with the work of [14], where, at run-time, new
bridge rules can be “observed”, i.e., learned from outside. Such rules can be added to
previous ones, or can replace them with a new version, with a check on consistency
among bridge-rules conclusions after the update. This work is complementary with our
proposal, where new bridge rules are generated inside a context.
Overall, we propose enhancements which are not in conflict with existing proposals
for MCSs which evolve in time [6, 15, 14], but rather either generalize such proposals
or, at least, can be combined with them. In what follows, we first recall the MCS ap-
proach. Then, using a motivating scenario, we propose some variations, enhancements,
and extensions to basic MCSs. Finally, we shortly discuss the complexity of the en-
hanced framework and conclude. In the Appendix, we propose an example of use of the
enhanced approach, in reference to the motivating scenario.
2 Bridge Rules and Multi-Context Systems
Heterogeneous MCSs have been introduced in [13] in order to integrate different in-
ference systems without resorting to non-classical logical systems. Later, the idea has
been further developed and generalized to non-monotonic reasoning domains —see, for
instance, [3–6, 16] among many. (Managed) MCSs are designed for the construction of
systems that need to access multiple (heterogeneous) data sources, called contexts. The
information flow is modeled via bridge rules, whose form is similar to Datalog rules
with negation where, however, each element in their “body” explicitly includes the in-
dication of the contexts from which each item of information is to be obtained. To
represent heterogeneity of sources, each context is supposed to be based on its own
logic, defined in a very general way [4]. A logic L defines its own syntax as a set F of
possible formulas (or KB -elements) under some signature possibly containing, predi-
cates, constants and functions. As usual, formulas are expressions built upon the idea of
atom, that is, the application of a predicate to a number n (the predicate arity) of terms.
The latter, in their turn, can be variables, constants, or compound terms using function
symbols, as usual. A term/atom/formula is ground if there are no variables occurring
therein. A logic is relational if in its signature the set of function symbols is empty,
so its terms are variables and constants only. Formulas can be grouped to form some
knowledge base, kb ∈ 2F . The set of all knowledge bases for L is defined as some
KB ⊆ 2F . The logic also defines beliefs or data (usually, ground facts) that can be de-
2
rived as consequences from a given kb ∈ KB . The set Cn represents all possible belief
sets in logic L. Finally, the logic specification must also define some kind of inference
or entailment. This is done by defining which belief sets are acceptable consequences
of a given kb ∈ KB with a relation ACC ⊆ KB × Cn. Thus, ACC (kb, S) means that
belief set S is an acceptable consequence of knowledge base kb. We can also use ACC
as a function ACC : KB → 2Cn where S ∈ ACC (kb) is the same as ACC (kb, S) as a
relation. To sum up, logic L can be completely specified by the triple hKB , Cn, ACC i.
A multi-context system (MCS) M = {C1 , . . . , Cn } is a set of n = |M | contexts,
each of them of the form Ci = hci , Li , kbi , bri i, where ci is the context name (unique
for each context, or number i if omitted), Li = hKB i , Cni , ACC i i is a logic, kbi ∈
KB i a knowledge base, and bri is a set of bridge rules, each of them ρ ∈ bri like
s ← A1 , . . . , Ah , not Ah+1 , . . . , not Am (1)
where the left-hand side s is called the head, denoted as hd(ρ), the right-hand side is
called the body, denoted as body(ρ), and the comma stands for conjunction. We define
the positive (resp. negative) body as body + (ρ) = {A1 , . . . , Ah } (resp. body − (ρ) =
{Ah+1 , . . . , Am }). The head hd(ρ) = s is a formula in Li such that (kbi ∪{s}) ∈ KB i .
Each element Ak in the body has the form (cj : p) for a given j, 1 ≤ j ≤ |M |, and
can be seen as a query to the (possibly different) context Cj ∈ M whose name is cj , to
check the status of belief p (a formula from Lj ) with respect to the current belief state
(defined below) in Cj . When the query is made in the context j = i we will omit the
context name, simply writing p instead of (ci : p). A relational MCS [12] is a variant
where all the involved logics are relational, and aggregate operators in database style
(like sum, count, max, min), are admitted in bridge-rule bodies.
A belief state (or data state) S of an MCS M is a tuple S = (S1 , . . . , Sn ) such
that for 1 ≤ i ≤ n = |M |, Si ∈ Cni . Thus, a data state associates to each context
Ci a possible set of consequences Si . A bridge rule ρ ∈ bri of context Ci ∈ M is
applicable in belief state S when, for any (cj : p) ∈ body + (ρ), p ∈ Sj , and for any
(ck : p) ∈ body − (ρ), p 6∈ Sk ; so, app(S) is the set of heads from those bridge rules
applicable in S.
In managed MCSs (mMCSs)4 the conclusion s, which represents the “bare” bridge-
rule result, becomes o(s), where o is a special operator. The meaning is that s is pro-
cessed by operator o, that can perform any elaboration, such as format conversion,
belief revision, etc. More precisely, for a given logic L with formulas F = {s ∈
kb | kb ∈ KB }, a management base is a set of operation names (briefly, operations)
OP , defining elaborations that can be performed on formulas. For a logic L and a man-
agement base OP , the set of operational statements that can be built from OP and F is
F OP = {o(s) | o ∈ OP, s ∈ F }. The semantics of such statements is given by a man-
OP
agement function, mng : 2F × KB → KB , which maps a set of operational state-
ments and a knowledge base into a (possibly different) modified knowledge base5 . Now,
each context Ci = hci , Li , kbi , bri , OPi , mngi i in an mMCS is extended to include its
4
For the sake of simplicity, we define mMCS simply over logics instead of “logic suite” as done
in [5], where one can select the desired semantics among a set of possibilities.
5
We assume a management function to be deterministic, i.e., to produce a unique new knowl-
edge base.
3
Fig. 1. F&K System: General Architecture
own management function mngi which is crucial for knowledge incorporation from ex-
ternal sources and can be non-monotonic. The application of the management function
mngi to the result of the applicable rules must be acceptable with respect to ACCi . We
say that a belief state S is an equilibrium for an mMCS M iff, for 1 ≤ i ≤ |M |,
Si ∈ ACCi (mngi (app(S), kbi )) (2)
Namely, we (i) apply all the bridge rules of Ci that are applicable in the belief state
S; (ii) apply the management function which, by incorporating bridge-rule results into
Ci ’s knowledge base kbi , computes a new knowledge base kb0i ; and, finally, (iii) deter-
mine via ACCi the set of acceptable sets of consequences of kb0i . In an equilibrium,
such a set includes Si , i.e., an equilibrium is “stable” w.r.t. bridge-rule application.
Conditions for existence of equilibria and the complexity of deciding equilibrium
existence for mMCS have been studied [3]; roughly speaking, such complexity de-
pends on the complexity of computing formula (2) for each Ci ∈ M . Algorithms for
computing equilibria have been recently proposed [4, 10] but, in practice, they are only
applicable when open-access to contexts’ contents is granted. For practical purposes,
one will often provisionally assume that equilibria exist, and that they do not include
inconsistent data sets. It has been proved that such local consistency is achieved when-
ever all management functions are (lc-) preserving, i.e., if they always determine a kb0
which is consistent.
3 Proposed Extensions
Below we introduce some enhancements to the mMCS paradigm. We devised the pro-
posed extensions in the perspective of the application of mMCSs to Cyber-Physical Sys-
tems (CPS). In Fig. 1 we depict the scenario outlined in [1], concerning “FRIENDLY &
KIND with your Health” (F&K), kind Cyber-Physical Systems tailored for applications
in the E-Health field. In an F&K system, an mMCS is considered to be an essential part
of the system engine. Thus, for actual implementation of F&Ks and more generally of
4
intelligent logically-based CPS operating in the “Internet of Things”, issues related to
the concrete modalities of bridge-rule instantiation and execution need to be considered.
3.1 Update Actions and Timed Equilibria
Bridge rules as defined in mMCSs are basically a reactive device, as a bridge rule is ap-
plied whenever applicable. In dynamic environments, however, a bridge rule in general
will not be applied only once, and it does not hold that an equilibrium, once reached,
lasts forever. In fact, in recent extensions to mMCS, contexts are able to incorporate
new data items coming from observations, so that a bridge rule can be, in principle,
re-evaluated upon new observations. For this purpose, two main approaches have been
proposed for this type of mMCSs: so-called reactive [6] and evolving [15] multi-context
systems. A reactive MCS (rMCS) is an mMCS where the system is supposed to be
equipped with a set of sensors that can provide observations from a set Obs. Bridge
rules can refer now to a new type of atoms of the form o@s, being o ∈ Obs an observa-
tion that can be provided by sensor s. A “run” of such system starts from an equilibrium,
and consists in a sequence of equilibria induced by a sequence of sets of observations.
In an evolving MCS (eMCS), instead, there are special observation contexts where the
observations made over time may cause changes in each context knowledge base. As
for the representation of time, different solutions have been proposed. For instance, [6]
defines a special context whose belief sets on a run specify a time sequence. Other pos-
sibilities assume an “objective” time provided by a particular sensor, or a special head
predicate in bridge rules whose unique role is adding timed information to a context.
However, in the general case of dynamic environments, contexts can be realistically
supposed to be able to incorporate new data items in several ways, including interaction
with a user and with the environment. We thus intend to propose extensions to explicitly
take into account not only observations but, more generally, the interaction of contexts
with an external environment. Such an interaction needs not to be limited to bridge
rules, but can more generally occur as part of the context’s reasoning/inference process.
We do not claim that the interaction with an external environment cannot somehow
be expressed via the existing approaches to MCSs which evolve in time [6, 15, 14];
however, it cannot be expressed directly; in view of practical applications, we introduce
explicit and natural devices to cope with this important issue.
We proceed next to define a new extension called timed MCS (tMCS). In a tMCS,
the main new feature is the idea of (update) action. For each context Ci , we define a set
act i of elementary actions, where each element π ∈ act i is the name of some action or
operation that can be performed to update context Ci . We allow a subset Obsi ⊆ acti
for observing sensor inputs as in [6]. A compound action (action, for short) Πi is a set
Πi ⊆ act i of elementary actions that can be simultaneously applied for context Ci . The
application of an action to a knowledge base is ruled by an update function:
Ui : KBi × 2act i → 2KBi \ {∅},
so that kbi ∈ Ui (kbi , Πi ) means that the “new” knowledge base kb0i is a possible result
0
of updating kbi with action Πi under function Ui . We thus assume Ui to encompass
all possible updates performed to a module (including, for instance, sensor inputs, up-
dates performed by a user, consequences of messages from other agents or changes
determined by the context’s self re-organization). Note that Ui (kbi , Πi ) is (possibly)
5
non-derterministic, but never empty (some resulting kb0i is always specified). In some
cases, we may even leave the knowledge base unaltered kbi ∈ Ui (kbi , Πi ). Notice that
update operations can be non-monotonic.
In order to allow arbitrary sequences of updates, we assume a linear time repre-
sented by a sequence of time points {tT }T ≥0 indexed by natural numbers T ∈ N and
representing discrete states or instants in which the system is updated. The elapsed time
between each pair of states is some real quantity δ = tT+1 − tT > 0. Given T ∈ N
and context Ci , we write kbi [T ] and Πi [T ] to respectively stand for the knowledge base
content at instant T , and the action performed to update Ci from instant T to T + 1.
We define the actions vector at time T as Π[T ] = (Π1 [T ], . . . , Πn [T ]). Finally, Si [T ]
denotes the set of beliefs for context Ci at instant T whereas, accordingly, S[T ] denotes
the belief state (S1 [T ], . . . , Sn [T ]).
Definition 1 (timed context). Let Ci = hci , Li , kbi , bri , OPi , mngi i be an mMCS
context. The corresponding timed context w.r.t. an initial belief state S is defined as:
– Ci [0] = hci , Li , kbi [0], bri , OPi , mngi , act i , Ui i
– Ci [T +1] = hci , Li , kbi [T +1], bri , OPi , mngi , act i , Ui i, for T ≥ 0
where kbi [0] := kbi and S[0] := S, whereas kbi [T +1]:=mngi (app(S[T ]), kb0 ) and
kb0 ∈ Ui (kbi [T ], Πi [T ]).
Definition 2. We let a tMCS at time T be M [T ] = {C1 [T ], . . . , Cn [T ]}.
The initial timed belief state S[0] can possibly be an equilibrium, according to orig-
inal mMCS definition. Later on, however, the transition from a timed belief state to the
next one, and consequently the definition of an equilibrium, is determined both by the
update operators and by the application of bridge rules. Therefore:
Definition 3 (timed equilibrium). A timed belief state of tMCS M at time T +1 is a
timed equilibrium iff, for 1 ≤ i ≤ n it holds that Si [T +1] ∈ ACCi (kbi [T +1]).
The meaning is that a timed equilibrium is now a data state which encompasses
bridge rules applicability on the updated contexts’ knowledge bases. As seen in Def. 1,
applicability is checked on belief state S[T ], but bridge rules are applied (and their re-
sults incorporated by the management function) on the knowledge base resulting from
the update. The enhancement w.r.t. [6] is that the management function keeps its origi-
nal role concerning bridge rules, while the update operator copes with updates, however
and wherever performed. So, we relax the limitation that each rule involving an update
should be a bridge rule, and that updates should consist of (the combination and elabo-
ration of) simple atoms occurring in bridge bodies. Our approach, indeed, allows update
operators to consider and incorporate any piece of knowledge; for instance, an update
can encompass table creation and removal in a context which is a relational database
or addition of machine-learning results in a context which collects and processes big
data. In addition we make time explicit thus showing the timed evolution of contexts
and equilibria, while in [6] such an evolution is implicit in the notion of system run.
3.2 Bridge Rule Grounding and Activation
In the original definition of mMCSs, bridge rules are ground by definition. In [5], it
is literally stated that [in their examples] they “use for readability and succinctness
6
schematic bridge rules with variables (upper case letters and ‘ ’ [the ’anonymous’
variable]) which range over associated sets of constants; they stand for all respective
instances (obtainable by value substitution)”. However, the practical method for ob-
taining such ground instances remains to be seen, especially since the basic definition
of mMCS does not require either knowledge bases or bridge rules to be finite sets.
Moreover, in the original definition, bridge-rule application is reactive: a bridge rule is
applied whenever applicable. However, according to a context’s own logic, other pat-
terns of application might be defined, in principle; for instance, those introduced in [8].
In this section, we formally specify reasonable modalities for bridge-rules ground-
ing and for proactive, rather than reactive, application. The issue of bridge-rule ground-
ing has been discussed in [2] for relational MCSs where, however, the grounding of
bridge rules is performed over a carefully defined finite domain, composed of constants
only. As the authors observe, “...computing equilibria and answering queries on top
is not a viable solution”. So, they assume a given MCS to admit an equilibrium, and
define a query-answering procedure based upon some syntactic restrictions on bridge-
rule form. Such kind of limitation, which is common in logic programming approaches,
prescribes that: (i) in the body of a rule, positive literals occur (in a left-to-right order)
before negative literals, and their order is relevant; (ii) every variable occurring in the
head of a non-ground bridge rule r also occurs in some positive literal of its body. We
embrace the suggestion that bridge-rule grounding may occur at run-time, so we adopt
the syntactic limitation. However, in bridge-rule grounding we intend to consider any,
even infinite, domain, and we intend to consider timed belief states. In principle, bridge
rules might be grounded over all terms that can be built over the signature of every
context’s underlying logic. This because mMCSs admit “value invention”, i.e., via the
results of bridge-rules application, beliefs (and their arguments) are propagated among
contexts; so, via a bridge rule a context may obtain a result involving constants and
terms previously not occurring therein. However, in each particular belief state it suf-
fices to consider terms that actually occur in the composing belief sets: such sets are
indeed those which determine bridge-rule applicability at that stage.
Definition 4. Let r ∈ bri be a non-ground bridge rule in a context Ci of a given mMCS
M with (timed) belief state S[T ]. A ground instance ρ of r w.r.t. S[T ] is obtained by
substituting every variable occurring in r with ground terms occurring6 in S[T ].
By a “ground bridge rule” we implicitly mean a ground instance of a bridge rule w.r.t. a
timed data state. We now redefine bridge-rule applicability, by first introducing proac-
tive activation. For each context Ci , let7
Hi [T ] = {s| there exists rule ρ ∈ bri with head hd(ρ) = s at time T }.
We introduce a timed triggering function, tri [T ] : KBi → 2Hi [T ] , which specifies
(via their heads) which bridge rules are triggered at time T , and so, by performing some
reasoning over the present knowledge base contents. Since Hi [T ] can be in general an
infinite set, tri [T ](·) may itself return an infinite set. However, in practical cases, it will
presumably return a finite set of rules to be applied at time T .
Definition 5. A rule ρ ∈ bri is triggered at time T iff hd(ρ) ∈ tri [T ](kbi [T ]).
6
Variables may occur in p of atoms (cj :p) in the body of r, in its head o(s), or in both.
7
Here, the dependency on T is fictitious. It will be relevant for bridge-rules patterns in Sec. 3.3.
7
Let grtri [T ] be the set of all ground instances of bridge rules which have been
triggered at time T , i.e., ρ ∈ grtri [T ] iff ρ is a ground instance w.r.t. S[T ] of some
non-ground r such that hd(ρ) ∈ tri [T ](kbi [T ]).
For an mMCS M , data state S[T ] and a ground bridge rule ρ, let S[T ] |= body(ρ)
represent that the rule body holds in belief state S[T ].
Definition 6. The set app(S[T ]) relative to ground bridge rules which are applicable
in a timed data state S[T ] of a given tMCS M [T ] = {C1 [T ], . . . , Cn [T ]} is defined as:
app(S[T ]) = {hd(ρ) | ∃T 0 ≤ T such that ρ ∈ grtri [T 0 ] and S[T ] |= body(ρ)}.
By the definition of app(·), a (ground instance of) a bridge rule can be triggered at
a time T 0 , but can then become applicable at some later time T ≥ T 0 . Thus, any bridge
rule which has been triggered remains in predicate for applicability, which will occur
whenever its body is entailed by some future data state. One alternative solution that
may seem equivalent to the proposed one is that of adding a “guard” additional positive
subgoal in a bridge-rule body, to be proved within the context itself. Such additional
literal would have the role of enabling bridge-rule application. However, in our proposal
a context is committed to actually apply bridge rules which have been triggered as soon
as they will (possibly) be applicable while an additional subgoal should be re-tried at
each stage and, if non-trivial reasoning is involved, this may be unnecessary costly.
The definition of timed equilibria remains unchanged, apart from the modified
bridge-rule applicability. However, the added (practical) expressiveness is remarkable
as a context in the new formulation is not just the passive recipient of new information,
but it can reason about which bridge rules to potentially apply at each stage.
For practical applications, it may be useful to allow the grounding of literals in
bridge-rule bodies to be computed at run-time, whenever a bridge rule is actually ap-
plied. Such a grounding, and thus the bridge-rule result, can be obtained, for example,
by “executing” or “invoking” literals in the body (i.e., querying contexts) so as to obtain
the grounding of positive literals first, to be extended to negative ones.
Each positive literal (cj : p) in the body of a bridge rule may fail (i.e., cj will return a
negative answer), if none of the instances of p given the partial instantiation computed
so far is entailed by cj ’s present data state. Otherwise, the literal succeeds and the
other ones are (possibly) instantiated accordingly. Negative literals not (cj : p) make
sense only if p is ground at the time of invocation, and succeed if p is not entailed by
cj ’s present data state. In case either some literal fails or a non-ground negative literal
is found, the overall bridge rule evaluation fails without returning results. Otherwise
the evaluation succeeds, and the result can be elaborated by the management function
of the “destination” context. For modeling such a run-time procedural behavior, we
introduce potential applicability. Assuming that literals occurring in a bridge-rule body
are ordered left to right as they appear in the rule definition we can talk about first,
second, etc., positive/negative literal.
Definition 7. A ground bridge rule ρ ∈ grtri [T 0 ] for some T 0 , of the form (1) is poten-
tially applicable to grade k ≤ h at time T ≥ T 0 iff given a reduced version ρ0 of the
rule, of the form s ← A1 , . . . , Ak we have S[T ] |= body(ρ0 ).
Hence, a triggered bridge rule ρ is potentially applicable to grade k at time T if the
timed belief state at time T entails its first k positive literals. Plainly, we have:
8
Proposition 1. A ground bridge rule ρ is potentially applicable to grade k at time Tk
iff for every k 0 such that 1 ≤ k 0 ≤ k there exists Tk0 ≤ Tk such that ρ is potentially
applicable to grade k 0 at time Tk0 .
Proposition 2. Let ρ ∈ grtri [T 0 ] be a ground bridge rule, for some T 0 , of the form
(1) which is potentially applicable to grade h (or simply “potentially applicable”) at
time T ; then, hd(ρ) ∈ app(S[T ]) iff for every negative literal not (ck :p) in the body,
h + 1 ≤ k ≤ m, p 6∈ Sk [T ].
As the contexts composing an mMCS may be non-monotonic, a bridge rule ρ can
become potentially applicable at some time and remain so without being applicable, but
can become applicable at a later time if the atoms occurring in negative literals are no
longer entailed by the belief state at that state.
Notice that, in fact, in a practical distributed setting, literals in the body may suc-
ceed/fail at different times, depending on the various context update times, and upon
network delay. Let us therefore assume that success of a positive literal A (resp. neg-
ative literal not A) is annotated with the time-stamp when such success occurs, of the
form A[T ] (resp. of the form not A[T ]). So, for any bridge rule ρ ∈ grtri [T 0 ] like (1)
which is triggered at some time and then executed later, by the expression
s[Ts ] ← A1 [T1 ], . . . , Ah [Th ], not Ah+1 [Th+1 ], . . . , not Am [Tm ]
we mean that the rule has been executed left-to-right where each literal A[T ]/not A[T ]
has succeeded at time T and the result has been processed (via the management func-
tion) by the destination context (i.e., the one where the bridge rule occurs) at time Ts .
Clearly, we have T1 ≤ T2 ≤ ... ≤ Tm ≤ Ts . The above expression is called the
run-time version of rule ρ. It is successful if all literals succeed; otherwise it is failed.
In many practical cases we are able to assume a certain degree of persistence in
the system, i.e., that a literal which succeeds at a time Tr would then still succeed (if
re-invoked) at every subsequent time Tq with Tr ≤ Tq ≤ Ts (“local persistence as-
sumption” for rule ρ). This corresponds to assuming that, during the execution of a
bridge-rule, no changes in the involved contexts occur that would invalidate the bridge-
rule result before actual completion; so, this would enforce what we call the “coherent”
execution of a bridge rule. This assumption may sometimes be problematic in practice,
but in a distributed system such as an mMCS we cannot realistically assume the execu-
tion to be instantaneous. The assumption of persistence can be considered as reasonable
whenever the time amount required by the execution of a bridge rule is less than the av-
erage system change rate with respect to the involved belief elements. This is the usual
condition for artificial intelligence systems to be adequate w.r.t. the environment where
they are situated, rather that being “brittle”. There are possible ways of enforcing the
assumption. For instance, the contexts involved in a bridge rule execution might commit
to keep the involved belief elements untouched until the destination context sends an
“ack” to signal the completion of rule execution. This or other strategies to ensure co-
herent execution are deferred to the implementation of mMCS. Under this assumption
we have:
Theorem 1. Given a successful run-time version of a ground bridge rule ρ ∈
grtri (T̂ ), for some T̂ , of the form s[Ts ] ← A1 [T1 ], . . . , Ah [Th ], not Ah+1 [Th+1 ], . . . ,
9
not Am [Tm ]. Then, hd(ρ) ∈ app(S[Ts ]) and there exists T ≤ Tm such that hd(ρ) ∈
app(S[T ]). Moreover, for each i ≤ j there exists Ti0 ≤ Ti and Ti−1 ≤ Ti0 if i > 1 such
that ρ is potentially applicable to grade i at time Ti0 .
Proof. Thanks to the persistence of the system, fixing Ti0 = Ti , for each i ≤ j, suffices
to prove the first property, and fixing T = Tm suffices for the second one. The third one
follows in a straightforward way. t
u
The relevance of the above theorem is because, in practice, the execution involves
a non-ground rule r ∈ grtri [T̂ ] whose rule ρ mentioned therein is a ground instance.
Then, successful left-to-right execution of literals in the body of r will lead to dynami-
cally generate at run-time a successful run-time version of ρ. Specifically, the execution
of each non-ground positive literal in the body of r will generate a partial instantiation
which is propagated to the rest of the bridge-rule body.
3.3 Bridge-Rules Patterns
We now generalize and formalize for mMCS the enhanced form of bridge rules pro-
posed in [9] for logical agents. In particular, we replace context names in bridge-rule
bodies with context designators, which are special terms intended to denote a specific
kind of context. For instance, a literal such as doctorSmith:prescription(desease, P )
asking family doctor, specifically Dr. Smith, for a prescription related to a certain de-
sease, might become family doctor (d ):prescription(desease, P ) where the doctor to
be consulted is not explicitly specified. Each context designator must be substituted by a
context name prior to bridge-rule activation; in the example, a doctor’s name to be asso-
ciated and substituted by the context designators family doctor (d ) (which, therefore,
acts as a placeholder) must be dynamically identified; the advantage is, for instance, to
be able to flexibly consult the physician who is on duty at the actual time of the inquiry.
Definition 8. Let Ci be a context of an mMCS. A context designator m(k) is a term
where m is a fresh function symbol and k a fresh constant.8
A bridge-rule pattern φ is an expression of the form:
s ← (C1 :p1 ), . . . , (Cj :pj ), not (Cj+1 :pj+1 ), . . . , not (Cm :pm )
where each Cd can be either a constant or a context designator.
New bridge rules can thus be obtained and applied by replacing, in a bridge-rule
pattern, context designators via actual contexts names. So, contexts will now evolve
also in the sense that they may increase their set of bridge rules by exploiting bridge-
rule patterns:
Definition 9. Given an mMCS, each of the timed composing contexts Ci , 1 ≤ i ≤ n,
is defined, at time 0, as Ci [0] = hci , Li , kbi [0], bri , brpi , OPi , mngi , act i , Ui i, where
brpi is a set of bridge-rule patterns, and all the other elements are as in Def. 1.
Definition 10 (rule instance). An instance of the bridge-rule pattern φ ∈ brpi , for
1 ≤ i ≤ n, occurring in an mMCS, is a bridge rule r obtained by substituting every
context designator occurring in φ by a context name c ∈ {c1 , . . . , cn }.
8
Meaning that m and k belong to the signature of Li , but they do not occur in kbi or in bri .
10
The context names to replace a context designator must be established by suitable
reasoning in context’s knowledge base.
Definition 11. Given an mMCS M , any composing context Ci , for 1 ≤ i ≤ n, and
a timed data state S[T ] of M , a valid instance of a bridge-rule pattern φ ∈ brpi is a
bridge rule r̂ obtained by substituting every context designator in φ with a context name
c ∈ {c1 , . . . , cn } such that Si [T ] |= subsi (md (kd ), c), where subsi is a distinguished
predicate that we assume to occur in the signature of Li .
Let vinst(brpi )[T ] denote the set of valid instances of bridge rule patterns that can be
obtained at time T (for Ci ). The set of bridge rules associated with a context increases in
time with the addition of new ones which are obtained as valid instances of bridge-rule
patterns.
Definition 12. Given an mMCS, each of the timed composing contexts Ci , 1≤i≤n, is
defined, at time T +1, as:
Ci [T +1] = hci , Li , kbi [T +1], bri [T +1], brpi , OPi , mngi , act i , Ui i
with bri [T +1]=bri [T ]∪vinst(brpi )[T ], bri [0] = bri , and all the rest as in Def. 1.
All the other previously-introduced notions (equilibria, bridge-rule triggering and
applicability, etc.) remain unchanged. We do not need to modify bridge-rule trigger-
ing, having already introduced the time parameter in the definition of the set Hi [T ]
of bridge-rule heads at time T for context Ci . Notice that instantiation of bridge-rule
patterns corresponds to specializing bridge rules with respect to the context which is
deemed more suitable for acquiring some specific information at a certain stage of a
context’s operation. This evaluation is performed via the predicate subsi (md (kd ), c)
that can be defined so as to take several factors into account, among which, for in-
stance, trust and preferences. Also, this enhancement goes in the direction of dynamic
mMCS, where contexts can either join or leave the system during its operation. Such an
extension has been in fact advocated since [4].
Definition 13. We let a dynamic mMCS at time T be M [T ] = {C1 [T ], . . . , CnT [T ]},
where a timed belief state at time T is (as before) a tuple S[T ] = (S1 [T ], . . . , SnT [T ]).
The meaning is that the set of contexts which compose an mMCS may be differ-
ent at different times. Here one can see the utility of having a constant acting as the
context name; in fact, bridge-rule definition does not strictly depend upon the compo-
sition of M , as it would be by using integer numbers. Rather, applicability of a bridge
rule depends on the presence in the system of contexts with the names indicated in the
bridge-rule definition. Contexts can not only be added or removed, but also substituted
by new “versions” with the same name.
3.4 Complexity
For space reasons we just briefly discuss the complexity issues related to the proposed
approach. In general, the property that we may wish to check is whether a specific belief
of our interest will eventually occur at some stage in one (or all) timed equilibria of a
given mMCS. The formal definition is the following.
11
Definition 14. The problem Q∃ (respectively Q∀ ), consists in deciding whether, for a
given mMCS M under a sequence Π = Π[1], Π[2], . . . , Π[t] of update actions per-
formed at time instants 1, 2, . . . , t, and for a context Ci of M and a belief pi for Ci , it
holds that pi ∈ Si [t0 ] for some (respectively for all) timed equilibria S[t0 ] at time t0 ≤ t.
We resort, like [6], to context complexity as introduced in [11]. One has first to con-
sider a projected belief state Ŝ[t], which includes in the element Ŝi [t] the belief bi one
wants to query, and also includes for every element Ŝj [t] the beliefs that contribute to
bridge-rule applications which may affect pi (see [2] for an algorithm which computes
such sets of beliefs in the case of rMCSs). Then, the context complexity for Ci is the
complexity of establishing whether the element Ŝi [t] of such projected belief state is
a subset of the corresponding element Ŝi [t] of some timed equilibrium at time t. The
system context complexity of M is the smallest upper bound of the complexities of its
contexts. The system context complexity depends upon the logics of the contexts in M .
The problems Q∃ and Q∀ are undecidable for infinite update sequences, because
contexts’ logics can in general simulate a Turing Machine and thus such problems re-
duce to the halting problem. Better complexity results can, however, be obtained under
some restrictions. In particular, if we assume that all contexts Ci ’s knowledge bases
and belief states are finite at any stage, all update functions Ui , management functions
mngi and triggering functions tri are computable in polynomial time, and that the set
of bridge-rule patterns is empty and all bridge rules are ground, then we can proceed
as follows: a projected belief state can be guessed for each stage T ∈ N by a non-
deterministic Turing machine; then, the inclusion of each such projected belief state
Ŝ[T ] in some (all) timed equilibria S[T ] at that stage can be established by an oracle
under the system’s context complexity and, if the answer is positive, it must be checked
whether pi ∈ Ŝi [T ]; if not, subsequent updates must be performed (in polynomial time)
over Ŝ[T ], and the two checks must be repeated at each stage; this until either pi is
found or time T is reached, thus obtaining either a positive or a negative answer to the
Q∃ problem. Therefore, for finite update sequences the context complexity determines
the complexity of Q∃ and, complementarily, the complexity of Q∀ .
Reconsidering bridge-rule patterns and non-ground bridge rules we observe that by
assuming that subsi can be computed in polynomial time and produces a finite number
of substitutions for each context designator, and given a set of bridge-rule patterns of a
certain cardinality (size) ĉ, the size of the set of its valid instances is in general single ex-
ponential in ĉ. The same holds in principle for the grounding of bridge rules. However,
in our setting we assume that bridge-rule are executed and grounded in a Prolog-like
fashion: therefore, the computational burden for grounding is consequently smaller.
4 Concluding Remarks
In this paper we have proposed extensions to MCSs, aimed at practical application of
such systems. The enhanced customizable bridge rules that we have formalized here
have been succesfully experimented (though in a preliminar embryonic version) in a
significant case-study, reported in [7]. We intend to employ the proposed features in
the implementation, that will start in the near future, of an F&K Cyber-Physical Sys-
tem. This project will allow us to perform practical experiments in order to assess the
12
performance of this kind of systems, and to identify possible limitations and/or further
aspects that can be subjected to improvements.
References
1. F. Aielli et al. FRIENDLY & KIND with your health: Human-friendly knowledge-INtensive
dynamic systems for the e-health domain. In K. Hallenborg and S. Giroux, editors, Proc. of
A-HEALTH at PAAMS 2016., Comm. in Computer and Inf. Sci. Springer, 2016.
2. R. Barilaro, M. Fink, F. Ricca, and G. Terracina. Towards query answering in relational
multi-context systems. In P. Cabalar and T. C. Son, editors, Proc. of LPNMR 2013, volume
8148 of LNCS, pages 168–173. Springer, 2013.
3. G. Brewka and T. Eiter. Equilibria in heterogeneous nonmonotonic multi-context systems. In
Proc. of the 22nd AAAI Conf. on Artificial Intelligence, pages 385–390. AAAI Press, 2007.
4. G. Brewka, T. Eiter, and M. Fink. Nonmonotonic multi-context systems. In Logic Program-
ming, Knowledge Representation, and Nonmonotonic Reasoning, volume 6565 of LNCS,
pages 233–258. Springer, 2011.
5. G. Brewka, T. Eiter, M. Fink, and A. Weinzierl. Managed multi-context systems. In Proc. of
IJCAI 2011, pages 786–791. AAAI, 2011.
6. G. Brewka, S. Ellmauthaler, and J. Pührer. Multi-context systems for reactive reasoning in
dynamic environments. In T. Schaub, editor, Proc. of ECAI 2014. AAAI, 2014.
7. S. Costantini. ACE: a flexible environment for complex event processing in logical agents.
In EMAS 2015, Revised Selected Papers, volume 9318 of LNCS. Springer, 2015.
8. S. Costantini. Knowledge acquisition via non-monotonic reasoning in distributed heteroge-
neous environments. In M. Truszczyński, G. Ianni, and F. Calimeri, editors, Proc. of LPNMR
2013, volume 9345 of LNCS. Springer, 2015.
9. S. Costantini and A. Formisano. Augmenting agent computational environments with quan-
titative reasoning modules and customizable bridge rules. In N. Osman and C. Sierra, editors,
AAMAS 2016 Best Workshop Visionary Papers, volume 10003 of LNCS, 2016.
10. M. Dao-Tran, T. Eiter, M. Fink, and T. Krennwallner. Distributed evaluation of nonmono-
tonic multi-context systems. J. of Artificial Intelligence Research, 52:543–600, 2015.
11. T. Eiter, M. Fink, P. Schüller, and A. Weinzierl. Finding explanations of inconsistency in
multi-context systems. In F. Lin, U. Sattler, and M. Truszczyński, editors, Proc. of KR 2010.
AAAI, 2010.
12. M. Fink, L. Ghionna, and A. Weinzierl. Relational information exchange and aggregation
in multi-context systems. In Proc. of LPNMR 2011, volume 6645 of LNCS, pages 120–133,
2011.
13. F. Giunchiglia and L. Serafini. Multilanguage hierarchical logics or: How we can do without
modal logics. Artif. Intell., 65(1):29–70, 1994.
14. R. Gonçalves, M. Knorr, and J. Leite. Evolving bridge rules in evolving multi-context sys-
tems. In Proc. of CLIMA 2014, volume 8624 of LNCS, pages 52–69. Springer, 2014.
15. R. Gonçalves, M. Knorr, and J. Leite. Evolving multi-context systems. In Proc. of ECAI
2014, pages 375–380. IOS, 2014.
16. F. Roelofsen, L. Serafini, and A. Cimatti. Many hands make light work: Localized satisfi-
ability for multi-context systems. In R. López de Mántaras and L. Saitta, editors, Proc. of
ECAI 2004, pages 58–62. IOS Press, 2004.
13
A Appendix: An Example
In this Section we provide an example of use to illustrates the new features. We refer
to Example 2 in [6] where it is supposed that a user, Bob, suffering from dementia, is
able to live at home as an assisted living system, modeled by means of an rMCS, is able
to constantly track Bob’s position, and to detect and take care of emergencies (such as
Bob’s forgetting the stove on), on the basis of the data provided by sensors suitably
installed in Bob’s flat.
We generalize the rMCS to an F&K which is able to detect changes in Bob’s health
but also to notice anomalous behavior which might signify an impaired state. The input
can be provided by means of sensors, but also by recording and monitoring Bob’s activ-
ities via suitable telemedicine appliances, via, e.g., videocameras or via a personalized
assistant/monitoring agent (PMA) which might be incarnated, in different use-cases, in
a chatterbot/avatar on tv or on the mobile phone, or even in a social robot; in our view,
the PMA should be able to “transmigrate” from one form to another one according to
the situation which a patient is experimenting at a certain stage of her/his activities.
The patient’s PMA (in this case Bob’s), is assumed below to be modeled as a con-
text included in an mMCS where such context is in particular an agent defined in any
agent-oriented logic language [8].
Bob’s PMA pmabob might for instance, in case of slight variations of, e.g., blood
pressure or blood coagulation, re-adjust the quantity of medicament by consulting a
treatment knowledge base. In case of more relevant symptoms, the agent might consult
either Bob’s physician or a specialist, depending upon the relative importance of symp-
toms. In case of an emergency, for instance an hemorrhage, immediate help is asked
for. Clearly, the example is over-simplified and we do not aim at medical accuracy.
Following [6], in the example we assume that present “objective” time is made
available to each context as now (T ), where the current value of T is entered into the
system by a particular sensor. As mentioned before, literals in bridge-rule bodies with
no indication of a context are proved locally.
The following bridge rule associated to each patient’s PMA, and thus also to pmabob ,
is maybe the most crucial as it is able to ask for immediate help. The last literal in the
body concerns a context emergency center , which is supposed to be an interactive
component for emergency management able to send, for instance, an ambulance or a
helicopter for transportation to the hospital. The last literal in bridge-body will suc-
ceed whenever the emergency center context has received and processed the request,
which is sent in case severe symptoms have been detected. Those symptoms, and the
time when the request is issued, are communicated to the emergency center together
with the patient’s data (here, for simplicity, just a patient’s identification code). The
bridge rule head is processed by the management function so as to simply add to the
PMA’s knowledge base the record of the fact that help has been required at time T for
set of severe symptoms S.
help asked (bob, S , T , T1 , Th, H ) ←
now (T ), detected symptoms(S , T1 ), T 1 ≤ T,
patientid (bob, Bid ), emergency center : urgent help(Bid , S , T , Th, H )
The emergency center is provided with Bob’s patient’s id Bid and returns the time
T h and mean H by which the emergency will be coped with (e.g., an ambulance by
14
15 minutes). In order to ensure application of the rule only in case of a real emergency,
it will be triggered (by adding its head to trpmabob [T ]) only upon specific conditions,
e.g., if symptoms have occurred that can be considered to be severe for Bob’s particular
health conditions, and a physician is not already present or prompltly available. Upon
bridge-rule application, the management function will record the (ground) request for
help help asked (bob, S , T , T1 , Th, H ) that has been issued; this allows for instance
the PMA to check whether the promised assistance will actually arrive in time and
possibly to minister palliative treatment in the meanwhile.
The following bridge rule, potentially crucial for cardiophatic patients, will be trig-
gered by in case the blood coagulation value detected at time T is anomalous; this
implies that the quantity of anti-coagulant which Bob takes to treat his heart disease
must be rearranged accordingly. The correct quantity Q is obtained by the ATC (Anti-
Coagulant Center) knowledge base according to the last blood coagulation value V and
its variation D from previous records.
quantity(anticoagulant, Q) ←
coagulation val (V , D), patientid (bob, Bid ), atc : quantity(Bid , V , D, Q)
In case a patient’s health state is not really critical but is anyway altered, a physician
must be consulted. However, in case, e.g., of a simple flu the family doctor suffices,
while if there are symptoms that might be related to a more serious condition then a
specialist (e.g., a cardiologist) should be consulted. Thus, there will be a bridge-rule
pattern of the following form, where a physician can be consulted for condition C.
Again, the management function will record the request having been sent; the last literal
in the body will succeed, when the rule is dynamically executed, as soon as the doctor
receives the request.
call physician(bob, T ) ←
now (T ), condition(bob, T , C ),
patientid (bob, Bid ), mydoctor (d ) : consultation needed (Bid , C , T )
The physician, represented by the context designator mydoctor (d ), should however
be determined according to C. This can be done by suitably augmenting the definition
of the distinguished predicate subspmi bob , for instance, as follows. The notation ’ ’
indicates a “don’t care” variable, as time is not taken into account here.
subspmi bob (mydoctor (d ), F ) ← family doctor (F ), condition(bob, , fever )
subspmi bob (mydoctor (d ), F ) ← family doctor (F ), condition(bob, , headache)
subspmi bob (mydoctor (d ), G) ← my cardiologist(G), condition(bob, , chestpain)
Thus, a valid instance of the bridge-rule pattern will be generated according to the
patient’s need, as evaluated by the patient’s PMI. The resulting bridge rule will then be
immediately executed. So for instance, if Bob has chest pain and the cardiologist who
has been following him is Dr. House, then the bridge rule below will be constructed and
triggered:
call physician(bob, T ) ←
now (T ), condition(bob, T , chest pain),
patientid (bob, Bid ), drHouse : consultation needed (Bid , chest pain, T )
15