The paper focuses on the problem of determining a priori the maximal response time of rule based programs. The response time analysis problem is an important problem, especially for real time systems. We study this problem in the context of OPS5 production systems. Two aspects of the response time of a program are investigated, the maximal number of rule firings and the maximal number of basic comparisons made by the Rete network during the execution of the program. The response time analysis problem is in general undecidable. However, a program terminates in a finite time if the rule triggering pattern of this program satisfies certain conditions. We present four such termination conditions for OPS5 production systems. An algorithm for computing an upper bound on the number of rule firings is then given. To have a better idea of the time required during execution, we present an algorithm that computes the maximal time required during the match phase in terms of the number of comparisons made by the Rete network. This measurement is sufficient since the match phase consumes about 90 percent of the execution time.

Real-time rule-based expert systems are embedded decision systems that must respond to changes in the environments within stringent timing constraints. Given a program p, the response time analysis problem is to determine the response time of p. This problem consists of: determining whether or not the execution of p always terminates in bounded time; and computing the maximal execution time of p. The Equational Logic (EQL) language is a simple language designed for real-time applications. It has been proved by A.K. Mok (1989) that the response time analysis problem is undecidable if the program variables have infinite domains, and is PSPACE-hard in the case where all of the variables have finite domains. However, we have observed that the use of a simple syntactic and semantic check on programs coupled with other techniques such as state space graph checks can dramatically reduce the time needed in the analysis. There are sets of syntactic and semantic constraint assertions such that if the set S of rules satisfies any of them, then the execution of S always terminates in bounded time. Each of these sets of syntactic and semantic constraint assertions is called a Special Form. The focus of the paper is on proving the existence of two Special Forms and determining tight response time upper bounds of EQL rule-based programs. For each known Special Form, an algorithm used to calculate the maximal response time of programs satisfying this Special Form is presented. Additionally, to enhance the applicability of the proposed algorithms, we show how the General Analysis Algorithm can be used with these algorithms.>

Real-time expert systems are embedded decision systems which must respond to changes in the environments within stringent timing constraints. A major problem impeding the use of rule-based expert systems in real-time environments is the difficulty in predicting the response time of these rule-based systems. In this paper, we tackle this problem with a fast, partially parallelizable response time analysis algorithm for a class of EQL rule-based programs with constant assignments in the action parts of the rules.

Real-time expert systems are embedded decision systems which must respond to changes in the environments within stringent timing constraints. Given a program p, the response time analysis problem is to determine the maximal response time of p. In this paper, we tackle this problem with a response time upper bound algorithm for a class of EQL rule-based programs whose variables range over finite domains, This algorithm computes a response tame upper bound of the given program by determining the maximal number of rule firings which result from the firings of individual rules enabled at the invocation.>