Databases Reference
In-Depth Information
-
company
(
c
) for each
c
∈
C
,
-
prod by
(
g,c
j
,c
k
),if
{
c
i
|
g
∈
G
i
}
{
c
j
,c
k
}
,where
c
j
and
c
k
may possibly
=
coincide,
-
contr by
(
c
i
,c
k
,c
m
,c
n
),if
c
i
∈
C
and
O
i
=
{
c
k
,c
m
,c
n
}
,where
c
k
,
c
m
,and
c
n
are not necessarily distinct.
We next present a program
P
st
, which characterizes this hard problem using only two
rules:
r
1
:
strat
(
Y
)
∨
strat
(
Z
)
←
prod by
(
X,Y,Z
)
.
r
2
:
strat
(
W
)
←
contr by
(
W, X, Y, Z
)
,strat
(
X
)
,strat
(
Y
)
,strat
(
Z
)
.
Here
strat
(
X
) means that company
X
is a strategic company. The guessing part of the
program consists of the disjunctive rule
r
1
, and the checking part consists of the normal
rule
r
2
. The program
P
st
is surprisingly succinct, given that Strategic Companies is a
hard problem.
The program
P
st
exploits the minimization which is inherent to the semantics of
answer sets for the check whether a candidate set
C
of companies that produces all
goods and obeys company control is also minimal with respect to this property.
The guessing rule
r
1
intuitively selects one of the companies
c
1
and
c
2
that produce
some item
g
, which is described by
prod by
(
g,c
1
,c
2
). If there was no company con-
trol information, minimality of answer sets would naturally ensure that the answer sets
of
correspond to the strategic sets; no further checking would be needed.
However, in case control information is available, the rule
r
2
checks that no company
is sold that would be controlled by other companies in the strategic set, by simply re-
questing that this company must be strategic as well. The minimality of the strategic
sets is automatically ensured by the minimality of answer sets.
The answer sets of
F
st
∪{
r
1
}
F
st
∪P
st
correspond one-to-one to the strategic sets of the holding
described in
F
st
; a company
c
is thus strategic iff
strat
(
c
) is in some answer set of
F
st
∪P
st
.
An important note here is that the checking “constraint”
r
2
interferes with the guess-
ing rule
r
1
: applying
r
2
may “spoil” the minimal answer set generated by
r
1
.Forex-
ample, suppose the guessing part gives rise to a ground rule
r
3
:
strat
(
c
1)
∨
strat
(
c
2)
←
prod by
(
g,c
1
,c
2)
and the fact
prod by
(
g,c
1
,c
2) is given in
F
st
. Now suppose the rule is satisfied in the
guessing part by making
strat
(
c
1) true. If, however, in the checking part an instance of
rule
r
2
is applied which derives
strat
(
c
2), then the application of the rule
r
3
to derive
strat
(
c
1) is invalidated, as the minimality of answer sets implies that rule
r
3
cannot
justify the truth of
strat
(
c
1), if another atom in its head is true.
