Why a rule engine needs an execution policy
A diagnostic system may infer several possible actions from the same observations. If a battery is low, one rule may request charging; if its casing is damaged, another may prohibit charging and request inspection. The observations alone do not tell a machine which action to execute. The rule author must also specify how to identify eligible rules, how to choose among them, and what each action changes.
This section studies a small production-system model. Unlike a positive Horn closure, firing a rule can remove facts. Therefore later eligibility can depend on an earlier choice. The rules below express a deliberately chosen policy, not a claim that this policy is suitable for every real device. Real safety decisions need independently validated conditions and controls.
A precise execution model
Definition 25.1.1
(Rules, enabling and firing)
Let be a finite set of atoms and a finite set of rules. A state is a subset of . A rule has a finite positive condition , a delete set , an add set , and an integer priority . Assume . The rule is enabled at exactly when . Its firing changes the state to
Definition 25.1.2
(Conflict set and selection policy)
The conflict set is the set of enabled rules whose firing would actually change . At each step select a rule of maximum priority in this set. If several have the same priority, use a fixed total order on rule identifiers to select the first. Stop when the conflict set is empty. The fixed order makes the next state deterministic; it is a policy choice, not a theorem that the chosen action is best. Removing no-op firings avoids repeatedly firing a rule that changes nothing, but by itself does not ensure termination.
Definition 25.1.3
(Execution trace)
A trace records the initial state and, for every step, the selected rule, its satisfied condition , the facts actually removed and added , and the resulting state. It should also record competing rules and their priorities when explaining a conflict. In a real implementation, fact identifiers and evidence sources should be preserved separately from the logical state; identical facts from different observations need not have identical provenance. A record of one execution is not automatically a proof that no other policy could lead to a different result.
Theorem 25.1.4
(Termination from a decreasing rank)
Suppose there is a function such that every state-changing firing of every rule satisfies whenever the rule is enabled. Then every execution terminates after at most firings, for any initial state and any policy that selects from the conflict set at each step and stops exactly when it is empty. With the maximum-priority and fixed tie-breaking policy above, the entire terminating trace is unique for a given initial state.
Proof and what the hypothesis buys
Proof
(A decreasing rank bounds the number of steps)
Every step of an execution is state-changing by the definition of the conflict set. Hence the hypothesis makes the nonnegative integer rank decrease by at least one at each step. After steps it is at most ; therefore cannot exceed . Thus no execution can contain more than steps. Since an execution continues whenever the conflict set is nonempty, it reaches a state with an empty conflict set within that bound.
At a given state the finite conflict set is determined. If nonempty, its greatest priority exists, and the fixed identifier order selects exactly one of the tied rules. The transition formula then determines exactly one next state. Induction on the step number makes any two executions from agree until they stop. Termination establishes that this unique trace is finite. The proof does not show that different priority tables have the same terminal state, nor that the policy correctly represents the domain.
Proof X-ray
Finite states alone do not force termination
A finite state space guarantees a repeated state in an infinite run, not a halt. The decreasing rank rules out such a cycle. Its strict decrease must be checked for every enabled state-changing firing, not merely for the first trace tried in an example.
Worked trace: conflicting recommendations
Worked example 25.1.5
(Conflicting recommendations: inspection outranks charging)
Use atoms , meaning low battery, damage, charge, inspect and pending. Initially . The policy has two rules:
- : conditions , delete , add , priority 2.
- : conditions , delete , add , priority 1.
Both are enabled initially and both change the state. The conflict set is ; inspection wins because priority 2 exceeds 1. Firing gives . Both rules now lack , so execution stops. A trace explains both why inspection occurred and why charging did not: the selected inspection rule consumed the pending token. If alone had fired from (for example if were absent), the result would have been .
For this particular rule base choose if and otherwise. Every enabled firing removes and neither adds it, so the theorem applies. The token is a modeling device that permits at most one action in this episode; it is not a physical battery property. A new episode requires an explicit reset policy.
Worked example 25.1.6
(Ties and no-op firings)
Let . The rule has condition , delete set and add set ; the rule has condition , an empty delete set and add set . Both have priority 3, and the identifier order puts before . From both rules are enabled and both change the state, so the conflict set is and the tie is broken in favor of . Firing it gives , where neither rule is enabled, so the terminal state is . With the identifier order reversed, fires first and gives . There is enabled and changes the state, but would add the already present and delete nothing, so it is a no-op and is excluded from the conflict set. Hence fires and the terminal state is . A rank is , where is if the statement holds and otherwise: lowers the first term, and , whenever it changes the state, lowers the second. So bounds the run, and the two identifier orders use one and two firings respectively.
Worked example 25.1.7
(A run with no firings)
In the battery example start from , where the token is absent. Neither rule is enabled, so the conflict set is empty and execution stops at once with zero firings; the trace consists of the initial state alone. The rank is , consistent with a bound of zero firings. The empty trace does not say that charging or inspection is unnecessary: it says only that, under this policy, no rule is eligible without a pending token.
Concept lensAlgorithmic
Inference, decision and execution
The observations and can support competing candidate conclusions without contradiction in a positive inference layer. The decision layer chooses inspection under the stated priority. The execution layer removes and records the chosen action. These three layers answer different questions; displaying a derivation of charge as if charging actually occurred would misreport the trace.
Counterexamples and limits
Counterexample mode
A different priority can change the result
Reverse the two priorities while keeping the same initial state. Now fires first and produces , after which is disabled because is absent. The terminal state differs from the inspection result. Both executions terminate; termination and deterministic tie-breaking do not imply independence from policy.
Finite atoms and exclusion of no-ops also do not prevent oscillation.
Counterexample mode
Every step changes the state, yet the run never ends
Let one rule replace by and another replace by , each with the corresponding atom as its condition. Starting from , every step changes the state, but the two states alternate forever. No strictly decreasing natural-number rank exists for both transitions: it would require .
Common mistakes
Common mistake
(A fire-once restriction is a different semantics)
A rule that has fired previously may become enabled again after a state change. A blanket “fire each rule once” restriction can prevent loops, but it changes the semantics and can miss a legitimate later action. In the two-rule loop above, firing each rule once stops at after , so a state in which the first rule is enabled is now reported as terminal. Similarly, assigning a higher priority to a rule does not prove safety: priority only encodes an ordering selected by a designer. Audit the conditions, evidence, reset behavior and consequences separately.
Common mistake
(A plausible rank must be checked on every firing)
Taking looks natural, since states are finite. The rule with condition , delete set and add set sends to , and stays , so this does not decrease and the theorem cannot be applied with it. The failure of one candidate rank proves nothing about termination, and the success of a rank on one trace proves nothing either: strict decrease must be shown for every enabled state-changing firing in every state.
Exercises
Quick check
(In the battery example, let the initial state be and leave priorities unchanged. Give the conflict set, next state and terminal state. What changes if the initial state is ?)
List the enabled rules, then keep only those that change the state.
Solution · Answer
The conflict set at is ; it fires to and no rule is then enabled. From the conflict set is ; it fires to , which is terminal. The priority comparison matters only when there is more than one enabled state-changing rule.
Quick check
(Let and let one rule require and delete and add ; let the other require and delete and add . The priorities can be arbitrary. Prove all executions terminate and give a bound from . What if is the initial state?)
Define a rank that counts how much of the chain is still ahead.
Solution · Answer
Set . Replacing by lowers by at least one even if was already present; replacing by lowers it by one even if was already present. Both rules delete their own condition, and every enabled firing changes state. Thus the theorem applies to every initial state. From the rank is 2, giving at most two firings: . From the initial bound is 3, though either rule order reaches in at most three firings.
Quick check
(Two rules both require and delete . The first adds and the second adds . Both have priority 4. With identifier order first-before-second and initial state , find the trace. Now interpret as a fact and the two conditions and additions as Horn implications and . Is true in every model? Compare the Horn closure with the execution.)
Compare the execution with the closure of the same implications.
Solution · Answer
Both rules initially belong to the conflict set. The specified identifier order selects the first, yielding ; the second is then disabled and the trace ends. Under the stated Horn interpretation, and entail : it is true in every model, and the least Horn closure is . The execution ends in because its selected rule consumes . Absence from this execution does not even imply non-entailment, let alone entailment of negation.
Quick check
(Suppose a designer proposes as a termination rank. Give an enabled state-changing rule for which the proposed rank does not decrease, and explain what must be shown to use the theorem.)
Find one rule whose firing keeps the number of facts unchanged.
Solution · Answer
The rule requiring and deleting and adding takes to , so the state changes while stays 1. To use the theorem one must show strict decrease for every enabled state-changing firing in every state, as the theorem requires, with a nonnegative integer rank; checking a single sample trajectory is insufficient.