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

作者：Yoshikawa Hiyori; Hirai Hiroshi^*; Makino Kazuhisa

来源：Journal of Mathematical Psychology, 2017, 77: 82-93.

DOI：10.1016/j.jmp.2016.09.002

• Antimatroids
• Horn rules
• Implicational systems
• Learning spaces
• Knowledge spaces
• 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 of Horn rules with the unique maximal antimatroid 04(R) that is contained in the union-closed family X(R) naturally determined by R. We address algorithmic and Boolean function theoretic aspects on the association R -> A(R), where 5 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 dt(R). We show that this representation is essentially equivalent to the Korte-Lovasz 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.

• 出版日期2017-4