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 dependecy 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 befief (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.
• Asserions 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 assetion is non-monotonic is the OUT-List is not empty or if any assertion in the IN-List is non-monotonic.

Fig. A JTMS Assertion

Logic-Based Truth Maintence 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 contractiction here.
• If this happens network has to be reconstructed.

Assumption-Based Truth Maintence 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 contadictions arise and the ATMS can be pruned
  • Simply find assertion with no valid justifaction.