## A.1 SyntaxLogic Programs are built up from four disjoint classes of symbols, viz. A An A A q(X,Y) :- p(X,Y) & ~r(Y) A A rule in a logic program is The first rule below is safe. All of the variables that appear in the head appear in positive subgoals, and all of the variables that appear in the negative subgoal also appear in positive subgoals. r(X,Z) :- p(X,Y) & q(Y,Z) & ~r(X,Y) By contrast, the rules shown below are
Safety is important in defining the semantics of rules. It ensures that there are no unbound variables in deriving conclusions of rules and no unbound variables in determining whether or not negations are true. This will become clearer after we look at semantics below. In order to define boundedness and stratification, we need the notion of a dependency graph. The We say that q A relation in a logic program is
Unrestricted recursion can lead to difficulties, such as ambiguities or infinite answer sets. Boundedness and stratification eliminate these difficulties. Let us say that a subgoal in a rule is a For example, the following recursive logic program fragment is bounded. Let us assume that there are also some facts defining the
A logic program is For example, the following logic program is
As mentioned above, in GDL, we focus exclusively on programs that are safe, bounded, and stratified. While it is possible to extend the language to programs that are not safe or not bounded or not stratified, such extensions are not widely used in General Game Playing. ## A.2 SemanticsA logic program is, in effect, a compact representation of a set of ground atoms, which is called a To define entailment for programs without negation, we start with a dataset consisting of the ground atoms that are listed explicitly in the program. We then systematically iterate through program's rules and the dataset in search of an instance of a rule in which all of the subgoals are contained in the dataset, adding the head of each such rule instance to our dataset. This process continues until no new ground atoms can be found. It can be shown that this process terminates for every logic program that is safe and bounded. As an example, consider the following logic program. We have a few facts about about the parent(art,bob) parent(art,bud) parent(bob,cal) parent(bob,coe) parent(coe,dan) person(X) :- parent(X,Y) person(Y) :- parent(X,Y) grandparent(X,Z) :- parent(X,Y) & parent(Y,Z) We start the computation by initializing our dataset to the five ground atoms in the program. parent(art,bob) parent(art,bud) parent(bob,cal) parent(bob,coe) parent(coe,dan) Looking at the rules defining the person(art) parent(bob) parent(bud) parent(cal) parent(coe) parent(dan) Using the grandparent(art,cal) grandparent(art,coe) grandparent(bob,dan) At this point, it is not possible to find any additional conclusions, and so the process terminates. Our definition also deals with recursive rules. Suppose, for example, we were to add the following recursive rules to our program. One person is an ancestor(X,Y) :- parent(X,Y) ancestor(X,Z) :- parent(X,Y) & person(Z) & ancestor(Y,Z) Looking at the ancestor(art,bob) ancestor(art,bud) ancestor(bob,cal) ancestor(bob,coe) ancestor(cal,dan) With these additions, we can then derive the following additional data. ancestor(art,cal) ancestor(art,coe) ancestor(bob,dan) However, we are not done. Using the ancestor rule again, we can derive the following additional datum. ancestor(art,dan) At this point, none of the rules when applied to this collection of data produces any results that are not already in the set, and so the process terminates. The resulting collection of facts is the model. The presence of negated subgoals in a program complicates matters. Fortunately, our definition of entailment can be extended in a natural way to eliminate these problems. We start by associating a As an example, consider the following program. We say that a person satisfies the isparent(X) :- parent(X,Y) childless(X) :- person(X) & ~isparent(X) Using the notion of levels, we can extend our definition of entailment to programs with negative subgoals. We start by applying the definition we have just seen to obtain a model of all relations at level 0 of the stratification hierarchy. We then repeat the process for relations at higher levels. In so doing, we assume any negative subgoal is true at level n+1 if and only if the negated subgoal is To illustrate this, consider how we can use the rules above to compute the isparent(art) isparent(bob) isparent(coe) At this point, we have computed all relations at level 0, so can now compute childless(bud) childless(cal) childless(dan) If there were other relations at level 1, we could compute them in similar fashion and then move on to higher levels. In this case, there are no other relations at level 1 or any higher level, so we we are done. ## A.3 Open Logic ProgramsLogic programs as just defined are Formally, an The The Given an open logic program Finally, we define the meaning of an open logic program to be a function that maps each input model for the program into the corresponding output model. |