Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis,
Abstract
A rule-based system is presented for computer-aided circuit analysis. The set of rules, called EL, is written in a rule language called ARS. Rules are implemented by ARS as pattern-directed invocation demons monitoring an associative data base. Deductions are performed in an antecedent manner, giving EL's analysis a catch-as-catch-can flavor suggestive of the behavior of expert circuit analyzers. This style of circuit analysis is called propagation of constraints. The systems threads deduced facts with justifications which mention the antecedent facts and the rule used. These justifications may be examined by the user to gain insight into the operation of the set of rules as they apply to a problem. The same justifications are used by the system to determine the currently active data-base context for reasoning in hypothetical situations. They are also used by the system in the analysis failures to reduce the search space. This leads to effective control of combinatorial search which is called dependency-directed backtracking.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1976
- Accession Number
- ADA035719
Entities
People
- Gerald Jay Sussman
- Richard M. Stallman
Organizations
- Massachusetts Institute of Technology