A representation of antimatroids by Horn rules and its application to educational systems

We study a representation of an antimatroid by Horn rules, motivated by its recent application to computer-aided educational systems. We associate any set R of Horn rules with the unique maximal antimatroid A(R) that is contained in the union-closed family K(R) naturally determined by R. We address algorithmic and Boolean function theoretic aspects on the association R↦A(R), where R is viewed as the input. We present linear time algorithms to solve the membership problem and the inference problem for A(R). We also provide efficient algorithms for generating all members and all implicates of A(R). We show that this representation is essentially equivalent to the Korte-Lovász representation of antimatroids by rooted sets. Based on the equivalence, we provide a quadratic time algorithm to construct the uniquely-determined minimal representation. These results have potential applications to computer-aided educational systems, where an antimatroid is used as a model of the space of possible knowledge states of learners, and is constructed by giving Horn queries to a human expert.