Accession Number:

ADA179493

Title:

Sequentialization of Logic Programs.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1986-11-01

Pagination or Media Count:

82.0

Abstract:

Logical inference can be done in two directions either forwards from fact already known to other facts that may be of interest, or backwards from goals whose answers are needed to subgoals whose answers may be available. Some programs and languages use one direction exclusively because it is clearly better in the sense of computational efficiency for their purposes. There are, however, problems that are better solved by using some rules for forwards inference and others backwards. In theorem-proving and artificial intelligence work over the past two decades, numerous systems have been developed which allow inferences to be drawn either forwards or backwards, and a number of heuristics have evolved for deciding which direction to use a rule in. In this dissertation the author attempts to put these decisions on a quantitative footing, by developing algorithms for estimating the computational cost of a set of directions for rules, and applying standard optimisation techniques to derive the best set of choices. In ascending order of difficulty, it is assumed first that no forward rule uses any facts deduced by a backward rule then that directions can be chosen freely and finally that each rule can be split up and used partly forwards, partly backwards. Keywords Input Control decisions.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE