Sequentialization of Logic Programs.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1986
- Accession Number
- ADA179493
Entities
People
- Richard J. Treitel
Organizations
- Stanford University