Motivation
An expert rarely begins with a disconnected list of true sentences. Equipment belongs to categories, categories share properties, and familiar events follow recognizable patterns. A frame can collect an object's slots; a semantic network can record category links; a script can describe a permitted event sequence. These representations become useful for reasoning only when their links and omissions have precise meanings.
Consider a support system for printers. A laser printer may inherit a required power source from the broader printer category while overriding a typical connection method. A repair script may require isolation before opening a cover. An explanation should say whether a recommendation came from an observed symptom, a strict engineering rule, or a defeasible default. Treating all three sources as equally certain can produce an apparently coherent but unsafe recommendation.
We use finite models throughout so that algorithms, conflicts and explanations can be checked completely. The selected models are teaching constructions; they do not claim that all commercial shells use these particular inheritance or inference policies.
Definitions
Definition 5.1.1
(Class network and inherited types)
A class network is a finite directed acyclic graph. An edge means class is a subclass of . Write when or a directed path leads from to . This is a partial order; incomparable classes can share subclasses through multiple inheritance. For an object with explicitly asserted types , its inherited type set is , including itself.
Definition 5.1.2
(Frames and strict constraints)
A frame associates slot names with values or constraints. A strict slot constraint is a condition that every instance must satisfy, such as allowed voltages being in a specified set. Inherited strict constraints are combined by intersection, not by silently choosing one parent. An empty intersection reports an inconsistent frame. Distinguish this from a default value, which can be overridden according to a stated policy.
Definition 5.1.3
(Specificity frontier of a default)
For one slot, let a class contain at most one declared default value. For an object, collect declarations at all inherited classes. A declaration at is defeated if there is a declaration for the same slot at a strictly more specific inherited class . The remaining declarations form the specificity frontier. If their values agree, the default answer is that value; if they disagree, return an explicit conflict; if none exist, return unknown. An explicit object value takes priority but still must satisfy every strict constraint. A default answer is tentative and must be recomputed if types or declarations change.
Definition 5.1.4
(Finite event script)
A finite event script is a deterministic finite-state machine with a partial transition function. States record progress, symbols record observed event types, and a sequence is accepted when every transition is defined and the final state lies in . Missing transitions reject a sequence; they do not invent a missing event. Rich natural-language scripts may include roles and typical omissions, but this finite model deliberately treats only recorded event order.
Definition 5.1.5
(Frozen rule model and recommendation)
For the rule engine, freeze the resolved frame facts for one run, combine them with explicit observations, and use a finite ground atom universe . Rules have positive premises and one positive conclusion. Negative observations, if needed, are represented by distinct atoms such as power-absent; absence of power-present is not that atom. Constraints can separately forbid incompatible pairs. A recommendation is a logical consequence of the frozen model, with its evidential assumptions attached.
Theorem/Proposition
Proposition 5.1.6
(Finite inheritance is order independent under the stated policy)
Ancestor propagation on a finite acyclic class graph terminates and returns exactly the reachable ancestors, independently of traversal order. The specificity-frontier default policy is also independent of traversal order: its result is determined by the inherited declarations and the partial order. It returns one value precisely when its nonempty frontier has only that value. This does not assert that adding new types preserves earlier default answers.
Theorem 5.1.7
(Terminating goal-directed evaluation with shared dependencies)
For a finite positive ground rule base and a goal atom , construct the relevant dependency set by starting at and recursively including every premise of every rule whose head is already included. On this finite set, a tabled agenda procedure that fires every relevant rule once all its premises are established terminates and establishes exactly when the full rule base entails . Recording the first successful justification of each derived atom gives a finite acyclic explanation graph whose leaves are given facts or premise-free rules.
Concept lensStructural
Established atoms form a least model
The atoms the agenda establishes are exactly those in the smallest set that contains the given facts and is closed under the relevant rules: the least model of the slice. So "established" has a meaning independent of firing order, and an unsupported cycle such as stays outside that set.
Proof sketch or proof idea
Proof
(Marked propagation reaches exactly the ancestors)
For ancestor propagation, initialize a visited set with and process unvisited parent edges from every newly reached class. Every inserted class is reachable by construction. Conversely, induction on path length proves that every reachable ancestor is eventually inserted. Only finitely many classes can be inserted, and marking visited classes prevents repeated work. Acyclicity makes subclass specificity a genuine partial order; propagation alone could still terminate with visited marks on a cyclic graph, but the intended strict specificity would then need repair.
Proof
(The frontier of a finite partial order is nonempty)
To compute the default frontier, remove exactly those applicable declarations having another strictly more specific applicable declaration. That condition depends on reachability, not which parent was visited first. A finite nonempty partially ordered set has at least one minimal element: follow strict decreases until they stop. Thus a nonempty declaration set has a nonempty frontier. Equal frontier values give one tentative answer; distinct values exhibit the conflict. This proves the policy's claims without pretending that multiple inheritance always has a unique answer.
Proof
(Agenda counters, soundness and completeness)
For goal-directed inference, first build the dependency set using a stack and a visited table. Then count each rule's as-yet-unestablished distinct premises, seed the agenda with relevant given facts and empty-premise heads, and index each premise by the rules that use it. When an atom first becomes established, decrement the counters of its dependent rules. A counter reaching zero establishes its head if the head is new. Each atom enters the agenda at most once; each premise occurrence is processed at most once. The procedure therefore terminates in time linear in the relevant rule representation after the dependency graph is built.
Soundness follows because every fired rule has all its premises established. To prove completeness, consider the usual forward derivation in the full finite base. Whenever a relevant head is derived, every rule that could produce it has all its premises in the relevant set by construction. Induction on its first derivation round shows those premises, and then the head, will be established by the relevant agenda. Applying this to gives the result. Atoms outside the dependency set cannot be needed in a proof of using these rules.
For an explanation edge from a head to its supporting premises, every premise was established earlier than that newly inserted head. Establishment time strictly decreases along explanation edges. Hence no directed cycle is possible. A topological replay verifies the recommendation from its leaves. The graph is one sufficient derivation, not necessarily the shortest proof or a list of all possible reasons.
Proof X-ray
Tabling resolves repeated subgoals without treating cycles as evidence
A recursive backward interpreter might ask for , then , then again forever. The table stores the dependency instead of descending indefinitely. Only facts or already established premises trigger a conclusion. A cycle with no external support consequently remains unestablished. The algorithm combines backward relevance discovery with forward propagation inside that slice; it does not infer success merely because a goal reappears.
Worked examples
Worked example 5.1.8
(Multiple inheritance exposes rather than hides a conflict)
Let mobile-printer and office-printer be incomparable subclasses of printer, and let an object have both types. The first declares default connection wireless, the second wired. Both declarations lie on the frontier, so the result is conflict, regardless of parent order. A further type lab-printer below both can declare wired; if the object is also typed lab-printer, this defeats both ancestors and yields one value. If printer strictly permits voltage only in and a parent strictly permits only , their intersection is . A default voltage 110 cannot override that strict constraint.
Worked example 5.1.9
(A script checks an actual sequence)
Use states ready, isolated, open, closed, done. The only transitions are isolate, open-cover, close-cover, and restore-power in that order. State ready is initial and done accepting. The sequence isolate, open-cover, close-cover, restore-power is accepted. The sequence open-cover, isolate is rejected at its first symbol. By induction on prefix length, the machine's current state equals the result of replaying exactly the observed prefix. Calling isolation a typical event cannot justify silently inserting it when the evidence log omitted it.
Worked example 5.1.10
(An expert recommendation with a replayable explanation)
Facts are power-present, queue-stalled, and link-ok. Rules say power-present and queue-stalled imply software-check; software-check and link-ok imply restart-service; restart-service implies retest. A query for retest discovers these dependencies backward, then the agenda establishes software-check, restart-service, and retest in order. An unrelated toner-warning rule is excluded. The explanation for retest cites restart-service, whose premises cite software-check and link-ok, and finally the three observed facts. No rule proves that restarting will certainly repair every fault; it proves a recommendation under the encoded policy.
Common mistakes
Counterexample mode
Defaults are not monotone logical facts
Suppose class device defaults to connection wired, and mobile-device is a subclass of device with default wireless. An object initially known only as a device receives the wired tentative answer. Learning that it is also a mobile-device changes the frontier to that more specific declaration and replaces the earlier answer by wireless. A positive rule engine that merely appends wireless while retaining wired has mixed two incompatible semantics. Resolve defaults in a separate recomputed layer, or adopt a specifically defined nonmonotonic system.
Common mistake
(An explanation is not a causal claim)
A rule such as “queue stalled and link healthy implies inspect software” records a diagnostic policy, not a proof that the software caused the symptom. An explanation graph reports which premises justified a recommendation under the policy; it does not certify the physical cause.
Knowledge acquisition should ask domain experts for applicability conditions, counterexamples, required observations and consequences of error. It should then turn those answers into test cases, including unknown inputs and conflicting reports. A rule that worked on one memorable case may be too broad.
Common mistake
(Abandoning a goal after the first rule fails)
Backward evaluation that must prove failure has to explore every candidate rule for a head. Take rules and and the single fact . An interpreter that tries first, cannot establish , and abandons wrongly reports failure, whereas the second rule establishes . Conversely, under positive finite semantics one successful proof suffices for success.
For explanations involving defaults, attach the default's provenance so the reader can distinguish a measured value from an inherited assumption.
Common mistake
(A representable conflict is not a resolved conflict)
Keeping both power-present and power-absent as distinct atoms avoids automatic classical explosion in this positive engine, but it does not resolve their real-world conflict. A constraint monitor should flag the pair, and a decision layer should specify whether to request measurement, withhold a recommendation, or use another authorized action. The representation's consistency and the system's action policy are separate contracts.
Summary
Structured knowledge needs semantics for ancestry, strict constraints, tentative defaults and event order. Finite specificity frontiers make conflicts explicit rather than dependent on traversal order. Goal-directed dependency discovery with shared tables produces terminating positive-rule evaluation and replayable explanations. The reliability of an expert system depends on acquiring the right conditions and evidence as much as on implementing its inference engine.
Exercises
Quick check
(Classes A and B are incomparable children of C; D is below both. C defaults slot to 0, A to 1, and B to 2. Find the default for an object of type D before and after D declares . Explain why a parent visitation order must not decide the first answer.)
Solution · Answer
The initial frontier consists of A and B, because both defeat C and neither defeats the other. Their values disagree, so the answer is conflict. A declaration at D defeats all three ancestors and yields 3. Visiting A first and keeping its value would make the answer depend on storage order, contradicting the declared policy; all applicable maximal-specificity information must be considered.
Exercise 5.1.11
(A script has initial state 0, accepting state 2, transitions , , and . Characterize all accepted strings and prove your characterization.)
CoreProof
Solution(3)
- 1
Necessity of the shape
Key step
An accepted string must end in state 2. A run starts in 0, where only is defined, so it moves to 1. In state 1 only (staying) and (moving to 2) are defined. State 2 has no outgoing transitions, so any further symbol rejects. Hence an accepted string is , then some number of , then .
Because: State 2 has no outgoing transition, and only leaves state 0.
- 2
Sufficiency
For every , the string follows , then loops at 1, then , and ends in the accepting state 2.
- 3
State the language
∎The accepted strings are exactly for integers , including the shortest accepted string .
Quick check
(Use fact and rules , , , , and . Give the dependency slice and one explanation for goal . What happens for goal ?)
Solution · Answer
The relevant atoms for are . The first derivations are as a fact, from , from , and from and . This yields an acyclic explanation despite the unused reverse rule . For , the slice is , but its only rule requires already established. No fact seeds it, so the table remains false and the goal fails. A recursive cycle is not its own proof.
Exercise 5.1.12
(An acquired rule says symptom S implies fault F. Give a concrete finite counterexample showing why observing S does not establish a unique physical cause. Propose a revised recommendation rule and an explanation policy that does not make the unjustified causal claim.)
Core
Solution(3)
- 1
Build a counterexample
Key step
Take two devices, one with a disconnected cable and one with a stopped software queue. Both display S, but only the second has fault F. This finite interpretation falsifies the unconditional implication from S to F.
- 2
Revise the rule
A revised policy can say that S and verified-link-ok imply inspect-software, provided the expert has validated that recommendation.
- 3
State the explanation policy
The explanation lists S, the link measurement and the policy rule, and labels the output as a next diagnostic action rather than a uniquely established cause. Further measurements remain necessary to identify the fault.