Accession Number:

AD0636251

Title:

A DATA STRUCTURE FOR DIRECTED GRAPHS IN MAN-MACHINE PROCESSING

Descriptive Note:

Annual rept.

Corporate Author:

COMPUTER COMMAND AND CONTROL CO WASHINGTON DC

Personal Author(s):

Report Date:

1966-06-20

Pagination or Media Count:

76.0

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.

Subject Categories:

  • Human Factors Engineering and Man Machine Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE