AND-OR Graph

Nodes labeled by component databases have sets of successor nodes each labeled by one of the components. These nodes are called AND nodes because in order to process the compound database to termination all of the component database must be processed to termination.  In the above figure 2,  this node here in order to process C B Z to termination, C,B and Z needs to be processed to termination. In order  to process BM to termination both B and M needs to be processed to termination; so  on and so forth. This type of termination which requires all the successors of single label to terminate for processing that single label is known as AND node.  Another important thing that one needs to realize is that the successor nodes are labeled by the result of rule application.

  Here in the next step in order to process C, we have either of two ways that is we can terminate C by terminating DL or we can terminate with  BM.  Here we can follow any of the successor not both. They are referred to as the ‘OR’ nodes. Because , in order to process a component database to termination , the database resulting from only either DL or BM must be processed to termination. These are referred to as ‘or’ nodes.

 The structure called AND-OR graphs  are useful for depicting the activity of production systems. So the decomposable production system if you see above has these nodes that is  AND  and OR are important because if a component database is AND  then all of the component databases need to be moved to termination. So, that is the AND node here …examples  of AND nodes in the above figure are

1. C B Z : C, B ,Z  (To process C B Z  all the three successors C,B,Z needs to be terminated)
2. Z: B,M,B (To process Z all the three successors B, M, B needs to be terminated)

 The above are the AND nodes, here all of them needs to be moved to the termination.

On the other hand , we also have  OR nodes  in the above figure .For example, In order to process the C we can terminate any of the successors (i.e., D,L or B,M).

So, finally we can say that the notion of decomposable production system encompass a technique often called problem Reduction in AI. We have reduced the problem of taking C B Z to termination. To the problem of taking C, B and Z individually to termination.