As rule-based expert systems (also known as knowledge-based systems) become increasingly adopted in new application domains such as real-time systems, ensuring that they meet stringent timing constraints in these safety-critical and time-critical environments emerges as a challenging problem. Unfortunately, rule-based expert systems are usually computationally expensive and slow. Moreover, they are considered less predictable and analyzable because of their context-sensitive control flow and possible non-determinism. However, there have been few attempts to formalize the question of whether a rule-based program has bounded response time.

This presentation considers the case where an expert system forms the decision module of a real-time monitoring and controlling system. This real-time system takes sensor input readings periodically, and the embedded expert system must produce, based on these input values and state values from previous invocations of the expert system, an output decision which ensures the safety and progress of the real-time system and its environment prior to the taking of the next sensor input values. Thus, the upper bound on the expert system's execution time cannot exceed the length of the period between two consecutive sensor input readings. Therefore, the first objective is to determine before run-time a tight upper bound on the execution time of the expert system in every invocation. The second objective is to optimize the expert system by modifying or resynthesizing the rule base if the execution time is found to exceed the specified timing constraint.