COMP4418, 2019 – Exercises
1 Answer Set Programming 1.1 Modelling
Let S = {s1,…,sn} be a set of sets. A set cover of S is a set C ⊆ S such that s∈S s = s∈C s. A k-set cover is a set cover of size k, that is, |C| = k.
For instance, for an input S = {{1, 2}, {2, 3}, {4, 5}, {1, 2, 3}}, there is a 2-set cover C = {{1, 2, 3}, {4, 5}} since s∈S s = {1, 2} ∪ {2, 3} ∪ {4, 5} ∪ {1, 2, 3} = {1, 2, 3} ∪ {4, 5} = s∈C s.
Write an ASP program that decides the k-Set-Cover problem: Input: a set of sets and a natural number k ≥ 0.
Problem: decide if there is a k-set cover.
Assume the input parameter S = {s1, . . . , sn} is encoded by a binary predicate s in the way that x ∈ si iff s(i,x). The input parameter k is given as constant symbol k. Use a unary predicate c to represent the output C in the way that si ∈ C iff c(i).
1
1.2 Semantics
Consider the following program P.
Determine the stable models of S.
S Reduct PS {a,b,c,d} a.
{a, b, c}
{a, b, d}
{a, c, d} {b, c, d} {a, b} {a, c} {a, d} {b, c} {b, d} {c, d} {a}
{b} {c} {d} {}
a.
c ← notb,notd. d ← a,notc.
Stable model?
#
2