Databases Reference
In-Depth Information
F
ra
be the collection of facts for input predicates
node
and
arc
encoding a
complete graph with
n
nodes.
below. Let
P
ra
is the following program:
r
1
:
blue
(
X,Y
)
∨
red
(
X,Y
)
←
arc
(
X,Y
)
.
r
2
:
←
red
(
X,Y
)
,red
(
X,Z
)
,red
(
Y,Z
)
.
r
3
:
←
blue
(
X,Y
)
,blue
(
X,Z
)
,blue
(
Y,Z
)
,blue
(
X,W
)
,
blue
(
Y,W
)
,blue
(
Z,W
)
.
Intuitively, the disjunctive rule
r
1
guesses a color for each edge. The first constraint (
r
2
)
eliminates the colorings containing a red clique (i.e., a complete graph) with 3 nodes,
and the second constraint (
r
3
) eliminates the colorings containing a blue clique with
4 nodes. The program
P
ra
∪F
ra
has an answer set if and only if there is a coloring
of the edges of the complete graph on
n
nodes containing no red clique of size 3 and
no blue clique of size 4. Thus, if there is an answer set for a particular
n
,then
n
is
not
R
(3
,
4),thatis,
n<R
(3
,
4). On the other hand, if
P
ra
∪F
ra
has no answer set,
then
n
R
(3
,
4). Thus, the smallest
n
such that no answer set is found is the Ramsey
number
R
(3
,
4).
≥
Strategic Companies.
In the examples considered so far, the complexity of the problems
is located at most on the first level of the Polynomial Hierarchy [100] (in NP or co-NP).
We next demonstrate that also more complex problems, located at the second level of
the Polynomial Hierarchy, can be encoded in ASP. To this end, we now consider a
knowledge representation problem, inspired by a common business situation, which is
known under the name
Strategic Companies
[101].
Suppose there is a collection
C
=
{
c
1
,...,c
m
}
of companies
c
i
owned by a holding,
aset
G
=
{
g
1
,...,g
n
}
of goods, and for each
c
i
wehaveaset
G
i
⊆
G
of goods
produced by
c
i
and a set
O
i
⊆
C
of companies controlling (owning)
c
i
.
O
i
is referred
to as the
controlling set
of
c
i
. This control can be thought of as a majority in shares;
companies not in
C
, which we do not model here, might have shares in companies as
well. Note that, in general, a company might have more than one controlling set. Let
the holding produce all goods in
G
,i.e.,
G
=
c
i
∈C
G
i
.
A subset of the companies
C
⊆
C
is a
production-preserving
set if the following
conditions hold: (1) The companies in
C
produce all goods in
G
, i.e.,
c
i
∈C
G
i
=
G
.
(2) The companies in
C
are closed under the controlling relation, i.e., if
O
i
⊆
C
for
C
must hold.
A subset-minimal set
C
,whichis
production-preserving
, is called a
strategic set
.A
company
c
i
∈
some
i
=1
,...,m
then
c
i
∈
C
is called
strategic
, if it belongs to some strategic set of
C
.
This notion is relevant when companies should be sold. Indeed, intuitively, selling
any non-strategic company does not reduce the economic power of the holding. Com-
puting strategic companies is on the second level of the Polynomial Hierarchy [101].
In the following, we consider a simplified setting as considered in [101], where each
product is produced by at most two companies (for each
g
∈
G
|{
c
i
|
g
∈
G
i
}|≤
2)and
each company is jointly controlled by at most three other companies, i.e.,
|
O
i
|≤
3 for
i
=1
,...,m
. Assume that for a given instance of Strategic Companies,
F
st
contains
the following facts:
