Open Problem: AnsProlog encoding of win and lose (Chs 2,4)

The goal here is to develop an AnsProlog program that has the same characterization of winning and losing as the following logic program with respect to the well-founded semantics.

win(X) ← move(X, Y), not win(Y). an arbitrary set of ‘move’ facts.

We will now give another characterization of this which does not appeal to the well-founded semantics.

1. We have a set of nodes.

2. We are given a set of facts about a binary predicate move. Intuitively, move(a, b) means that there is an available move from node a to node b.

3. A strategy S is a function from nodes to nodes such that S(X) = Y only if move(X,Y) is true.

4. Given two strategies S_{1} and S_{2}, and a node a we define the trajectory followed by alternatively applying S_{1} and S_{2} as: traj(a, S_{1}, S_{2}) = X_{0}^{a,S_{1},S_{2}}X_{1}^{a,S_{1},S_{2}} …, where

X_{0}^{a,S_{1},S_{2}} = a X_{k+1}^{a,S_{1},S_{2}} = S_{1}(X_{k}^{a,S_{1},S_{2}}) if k is even

= S_{2}(X_{k}^{a,S_{1},S_{2}}) if k is odd

5. The length of a trajectory X_{0}X_{1} … X_{k} is k.

6. A node a is said to be a winning node if there exists S_{1} such that for all S_{2} the sequence traj(a, S_{1}, S_{2}) terminates and its length is odd.

7. A node a is said to be a losing node if for all S_{1} there exists S_{2} such that the sequence traj(a, S_{1}, S_{2}) terminates and its length is even.

Question 1: Write an AnsProlog program Π whose answer set semantics corresponds to the win and lose above. (The solution to this is known.)

Question 2: Write an AnsProlog program Π which has a unique answer set corresponding to the win and lose above. (To the best of my knowledge, this is an open problem.)

Acknowledgement: Bertram Ludaescher first posed this question to me in July 2002. Later in August 2002 I discussed this with Vladimir Lifschitz and his group in Austin. The above formulation was developed during my presentation in Austin.