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

DOI10.1016/J.JMP.2016.09.002zbMATH Open1396.91660arXiv1508.05465OpenAlexW3101317532MaRDI QIDQ2403022FDOQ2403022

Kazuhisa Makino, Hiyori Yoshikawa, Hiroshi Hirai

Publication date: 15 September 2017

Published in: Journal of Mathematical Psychology (Search for Journal in Brave)

Abstract: We study a representation of an antimatroid by Horn rules, motivated by its recent application to computer-aided educational systems. We associate any set $mathcalR$ of Horn rules with the unique maximal antimatroid $mathcalA(mathcalR)$ that is contained in the union-closed family $mathcalK(mathcalR)$ naturally determined by $calR$. We address algorithmic and Boolean function theoretic aspects on the association $calRmapstomathcalA(mathcalR)$, where $calR$ is viewed as the input. We present linear time algorithms to solve the membership problem and the inference problem for $calA(calR)$. We also provide efficient algorithms for generating all members and all implicates of $calA(calR)$. We show that this representation is essentially equivalent to the Korte-Lov'{a}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.

Full work available at URL: https://arxiv.org/abs/1508.05465

zbMATH Keywords

knowledge spacesantimatroidsHorn ruleslearning spacesimplicational systemseducational systems

Mathematics Subject Classification ID

Knowledge representation (68T30) Combinatorial aspects of matroids and geometric lattices (05B35) Galois correspondences, closure operators (in relation to ordered sets) (06A15) Memory and learning in psychology (91E40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Learning conjunctions of Horn clauses
• Queries and concept learning
• The theory of convex geometries
• Reverse search for enumeration
• The decision problem for some classes of sentences without quantifiers
• On sentences which are true of direct unions of algebras
• How to build a knowledge space by querying an expert
• Extracting human expertise for constructing knowledge spaces: An algorithm
• Applying the basis of a knowledge space for controlling the questioning of an expert
• Learning Spaces
• A class of stochastic procedures for the assessment of knowledge
• The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
• Meet-distributive lattices and the anti-exchange closure
• A theory of finite closure spaces based on implications
• Construction and learnability of canonical Horn formulas
• The multiple facets of the canonical direct unit implicational basis
• Greedoids
• A circuit set characterization of antimatroids
• Ordered direct implicational basis of a finite closure system
• The prime stems of rooted circuits of closure spaces and minimum implicational bases
• Optimum basis of finite convex geometry
• The joy of implications, aka pure Horn formulas: mainly a survey
• On implicational bases of closure systems with unique critical sets.
• On the irredundant generation of knowledge spaces
• Matroids and antimatroids - a survey
• On alternative representations for knowledge spaces
• Knowledge Spaces
• On verifying and engineering the wellgradedness of a union-closed family
• Learning Spaces, and How to Build Them
• Largest extension of a finite convex geometry

Cited In (5)

• Compressed representation of learning spaces
• Optimum basis of finite convex geometry
• Two flags in a semimodular lattice generate an antimatroid
• Representations for the largest extension of a closure system
• Notes on join semidistributive lattices

Uses Software

• JBool

This page was built for publication: A representation of antimatroids by Horn rules and its application to educational systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403022)