Efficient Multiplication of Boolean Matrices and Algorithm for D-Class Computation

D-class is defined as a set of equivalent boolean matrices according to a given equivalence relation. The D-class computation requires the multiplication of three boolean matrices for each of all possible triples of boolean matrices. However, almost all the researches on boolean matrices focused on the efficient multiplication of only two boolean matrices and a few researches have recently been shown to deal with the multiplication of all boolean matrices. The paper suggests a mathematical theory that enables the efficient multiplication for all possible boolean matrix triples and the efficient computation of all D-classes, and discusses algorithms designed with the theory and their execution results.