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.
