Truth Maintenance Systems

Truth Maintenance Systems: 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.

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.