(8th-August-2020)
• There is an infinite loop in the top-down derivation if there is an atom a that is being proved as a subgoal of a. (Here we assume that being a subgoal is transitive; a subgoal of a subgoal is a subgoal). Thus, there can be an infinite loop only if the knowledge base is cyclic. A knowledge base is cyclic if there is an atom a such that there is a sequence of definite clauses of the form
• a ←...a1 ...
• a1 ←...a2 ...
• ...
• an ←...a ...
• (where if n=0 there is a single definite clause with a in the head and body).
• A knowledge base is acyclic if there is an assignment of natural numbers (non-negative integers) to the atoms so that the atoms in the body of a definite clause are assigned a lower number than the atom in the head. All of the knowledge bases given previously in this chapter are acyclic. There cannot be an infinite loop in an acyclic knowledge base.
• To detect a cyclic knowledge base, the top-down proof procedure can be modified to maintain the set of all ancestors for each atom in the proof. In the procedure in Figure 5.4, the set A can contain pairs of an atom and its set of ancestors.
Comments