RESPONSE-TIME ANALYSIS OF EQL REAL-TIME RULE-BASED SYSTEMS

Real-time rule-based expert systems are embedded decision systems that must respond to changes in the environments within stringent timing c onstraints. Given a program p, the response time analysis problem is t o determine the response time of p. This problem consists of 1) determ ining whether or not the execution of p always terminates in bounded t ime, and 2) computing the maximal execution time of p. The EQuational Logic (EQL) language is a simple language designed for real-time appli cations. It has been proved by Mok that the response time analysis pro blem is undecidable if the program variables have infinite domains, an d is PSPACE-hard in the case where all of the variables have finite do mains. However, we have observed that the use of a simple syntactic an d semantic check on programs coupled with other techniques such as sta te space graph checks can dramatically reduce the time needed in the a nalysis. There are sets of syntactic and semantic constraint assertion s such that if the set S of rules satisfies any of them, then the exec ution of S always terminates in bounded time. Each of these sets of sy ntactic and semantic constraint assertions is called a Special Form. T he focus of this paper is on proving the existence of two Special Form s and determining tight response time upper bounds of EQL rule-based p rograms. For each known Special Form, an algorithm used to calculate t he maximal response time of programs satisfying this Special Form is p resented. Additionally, to enhance the applicability of the proposed a lgorithms, we show how the General Analysis Algorithm can be used with these algorithms.