The common order-theoretic structure of version spaces and ATMSs

Carl A. Gunter, Teow Hin Ngair, Devika Subramanian

Research output: Contribution to journalArticlepeer-review


We demonstrate how order-theoretic abstractions can be useful in identifying, formalizing, and exploiting relationships between seemingly dissimilar AI algorithms that perform computations on partially-ordered sets. In particular, we show how the order-theoretic concept of an anti-chain can be used to provide an efficient representation for such sets when they satisfy certain special properties. We use anti-chains to identify and analyze the basic operations and representation optimizations 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 version space merging, and (2) develop new, simpler label-update algorithms for ATMSs with DNF assumption formulas.

Original languageEnglish (US)
Pages (from-to)357-407
Number of pages51
JournalArtificial Intelligence
Issue number2
StatePublished - Sep 1997
Externally publishedYes


  • ATMS
  • Admissibility
  • Anti-chains
  • Concept learning
  • Label update algorithms
  • Partial orders
  • Truth maintenance
  • Version spaces

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'The common order-theoretic structure of version spaces and ATMSs'. Together they form a unique fingerprint.

Cite this