Decision implication canonical basis: a logical perspective

•Introduce the notions of decision premise and decision implication canonical basis.•Show that the canonical basis is complete, non-redundant and minimal.•Present an algorithm to generate this canonical basis.

Due to its special role on logical deduction and practical applications of attribute implications, canonical basis has attracted much attention and been widely studied in Formal Concept Analysis. Canonical basis is constructed on pseudo-intents and, as an attribute implication basis, possesses of many important features, such as completeness, non-redundancy and minimality among all complete sets of attribute implications. In this paper, to deduce an analogous basis for decision implications, we introduce the notion of decision premise and form the so-called decision implication canonical basis. Furthermore, we show that the basis is complete, non-redundant and minimal among all complete sets of decision implications. We also present an algorithm to generate this canonical basis and analyze time complexity of this algorithm.