Implementations: Truth Maintenance Systems

Due to Lecture time limitation. This topic is not dealt with in any great depth. Please refer to the further reading section.

A variety of Truth Maintenance Systems (TMS) have been developed as a means of implementing Non-Monotonic Reasoning Systems.

Basically TMSs:

• all do some form of dependency directed backtracking
• assertions are connected via a network of dependencies.

Justification-Based Truth Maintenance Systems (JTMS)

• This is a simple TMS in that it does not know anything about the structure of the assertions themselves.
• Each supported belief (assertion) in has a justification.
• Each justification has two parts:
  • An IN-List -- which supports beliefs held.
  • An OUT-List -- which supports beliefs not held.

• An assertion is connected to its justification by an arrow.
• One assertion can feed another justification thus creating the network.
• Assertions may be labelled with a belief status.
• An assertion is valid if every assertion in the IN-List is believed and none in the OUT-List are believed.
• An assertion is non-monotonic is the OUT-List is not empty or if any assertion in the IN-List is non-monotonic.

Fig. 20 A JTMS Assertion

Logic-Based Truth Maintenance Systems (LTMS)

Similar to JTMS except:

• Nodes (assertions) assume no relationships among them except ones explicitly stated in justifications.
• JTMS can represent P and P simultaneously. An LTMS would throw a contradiction here.
• If this happens network has to be reconstructed.

Assumption-Based Truth Maintenance Systems (ATMS)

• JTMS and LTMS pursue a single line of reasoning at a time and backtrack (dependency-directed) when needed -- depth first search.
• ATMS maintain alternative paths in parallel -- breadth-first search
• Backtracking is avoided at the expense of maintaining multiple contexts.
• However as reasoning proceeds contradictions arise and the ATMS can be pruned
  • Simply find assertion with no valid justification.