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.
