| Popis: |
Grapple [1] is an expert system for graph theory investigation. Grapple embodies a model of research which encodes graph theory knowledge and reasoning gleaned from textbooks and practicing researchers. The model consists of five steps: I. Reaching the frontier; II. Exploration; III. Discovering regularity; IV. Conjecture formulation; V. Proof.Step I models the acquisition of foundational knowledge in the research domain. This includes specific knowledge about particular graphs, classes of graphs, and related theorems. In step II the knowledge gained in step I is used to generate data relating graphs, their properties, and theorems. Properties are computed for example graphs in certain classes. Graphs are matched with hypotheses to determine which graphs and theorems “belong” to each other. Step III checks for patterns in the results obtained in step II. A search is made for regularities between and within classes and among related theorems. Step IV is the heart of the model, the conjecture formulation process. In this step perceived regularities are recast as conjectures. The two primary difficulties are to determine a reasonable scope for the conjecture, that is, a hypothesis, and finding the correct statement of the perceived regularity, that is, a conclusion. Step V is proof. Formal theorem proving has a rich literature and is not discussed here.Much specific knowledge is captured in the model. This includes how to construct individual graphs and their representations, and a taxonomy of classes of graphs together with algorithms for determining membership. Also required is the knowledge of a wide range of graph theoretic properties together with means to determine their values for specific graphs. At a more abstract level there are theorems which describe attributes of graph classes, relate members of one class to members of another, and relate properties to other properties.In general, there is no smooth progression from step I to step V of the research process. This is reflected in Grapple's non-linear control mechanism. A set of rules are used to judge when a transition is made between one step and another. These rules capture metaknowledge about the research process and are based on anecdotal experiences with an expert graph theorist. Eight principles of control have been identified which guide the research process. |
