Jr. Chen et Amk. Cheng, RESPONSE-TIME ANALYSIS OF EQL REAL-TIME RULE-BASED SYSTEMS, IEEE transactions on knowledge and data engineering, 7(1), 1995, pp. 26-43
Citations number
33
Categorie Soggetti
Information Science & Library Science","Computer Sciences, Special Topics","Engineering, Eletrical & Electronic","Computer Science Artificial Intelligence
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.