Semantics of production systems (Q1110314)

What this paper shows is the worth of denotational semantics as a post- facto description tool. It would not have been possible to write a semantic description of a production system (PS) seven years ago because it was not fully understood what they were. Now that they have entered the pool of general programming techniques, they can be described succinctly by the lingua franca of computing formalism (deficiencies notwithstanding). The authors start with an informal, but fairly abstract, description of the nature of production systems which, in turn, motivates the construction of the semantic domains over which PSs operate. The basic entities are incomplete trees, which are used to describe the state of the search so far through the solution space, and the characteristic function of a PS is given as a mapping from search trees to a set of results. This is followed by an operational definition of a PS, focussing on search strategies, which is then refined into a denotational description (giving the set of all solutions) which is then further refined into what the authors term failure-success semantics. This last form is important because this corresponds to what most PSs do in practice, that is, produce a single answer. Although the semantics given does relate to PSs in practice, as noted above, there is no discussion (although breadth-first is briefly mentioned as a full search strategy) of search strategies in practice. Most production systems do not evaluate all possibilities, but rather make a selection (conflict resolution) and do not back up from that choice. However, such an analysis would be quite complicated. In summary, this paper is recommended reading if you have a semantics background and want to understand quickly and (fairly) precisely how PSs work. The notation is a little strange in places, but also quite perspicuous in others. As well as a number of curiosities in the use of English, there is an amusing neologism based on the misconception that the prefix ``in-'' creates the negative form (counterexample: flammable).