Rh. Wang et Ak. Mok, RESPONSE-TIME BOUNDS OF EQL RULE-BASED PROGRAMS UNDER RULE PRIORITY STRUCTURE, IEEE transactions on software engineering, 21(7), 1995, pp. 605-614
A key index of the performance of a rule-based program used in real-ti
me monitoring and control is its response time, defined by the longest
program execution time before a fixed point of the program is reached
from a start state. Previous work in computing the response-time boun
ds for rule-based programs effectively assumes that all rules take the
same amount of firing time. It is also assumed that if two rules are
enabled, then either one of them may be scheduled first for firing. Th
ese assumptions can result in loose bounds, especially in the case pro
grammers choose to impose a priority structure on the set of rules. In
this paper, we remove the uniform-firing-cost assumption and discuss
how to get tighter bounds by taking rule-priority information into acc
ount. We show that the rule-suppression relation we previously introdu
ced can be extended to incorporate rule-priority information. A bound-
derivation algorithm for programs whose potential-trigger relations sa
tisfy an acyclicity condition is presented, followed by its correctnes
s proof and an analysis example.