A DATA STRUCTURE FOR DIRECTED GRAPHS IN MAN-MACHINE PROCESSING
Abstract
This report describes research in information processing intended for application to man-machine communication processes. In order to allow a computer user to represent some problems more easily, we would like to let him name and define relations between information entities with which he deals, and then manipulate a large number of such relations stored by the computer. A set of statements on the relative desirability of various conditions is an example of a set of relations which the user might want to store and manipulate. The problem is that available representations for such sets of relations tend to be unwieldy and may require a great deal of processing for large numbers of relations. In order to make such a capability available, compact and easily- manipulated internal computer representations for large numbers of the various kinds of two-entity relations must be found. This report describes such a development for one basic logical form of relation, the transitive, anticommutative relation exemplified by ''precedes'', ''includes'', ''is greater than'', and similar phrases. The report describes a method for storing directed graphs (of transitive anticommutative relations) in a list-structured computer memory. There are three important features of this representation method: A method of dividing a graph into a number of strata based on the lengths of paths in the graph, a recursive decomposition technique which produces successively less complex versions of the graph, and a recursive search technique which utilizes the stratification and decomposition to extract information from the graph with a limited amount of processing effort.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 20, 1966
- Accession Number
- AD0636251
Entities
People
- Paul A. Jensen
- William C. Mann