THE COMMON ORDER THEORETIC STRUCTURE OF VERSION SPACES AND ATMSS

We demonstrate how order-theoretic abstractions can be useful in ident ifying, formalizing, and exploiting relationships between seemingly di ssimilar AI algorithms that perform computations on partially-ordered sets. In particular, we show how the order-theoretic concept of an ant i-chain can be used to provide an efficient representation for such se ts when they satisfy certain special properties. We use anti-chains to identify and analyze the basic operations and representation optimiza tions in the version space learning algorithm and the assumption-based truth maintenance system (ATMS). Our analysis allows us to (1) extend the known theory of admissibility of concept spaces for incremental v ersion space merging, and (2) develop new, simpler label-update algori thms for ATMSs with DNF assumption formulas. (C) 1997 Published by Els evier Science B.V.