불리언 행렬의 모노이드에서의 J 관계 계산 알고리즘

Algorithm for Computing J Relations in the Monoid of Boolean Matrices

Green's relations are five equivalence relations that characterize the elements of a semigroup in terms of the principal ideals. The J relation is one of Green's relations. Although there are known algorithms that can compute Green relations, they are not useful for finding all J relations in the semigroup of all n x n Boolean matrices. Its computation requires multiplication of three Boolean matrices for each of all possible triples of n x n Boolean matrices. The size of the semigroup of all n x n Boolean matrices grows exponentially as n increases. It is easy to see that it involves exponential time complexity. The computation of J relations over the 5 x 5 Boolean matrix is left an unsolved problem. The paper shows theorems that can reduce the computation time, discusses an algorithm for efficient J relation computation whose design reflects those theorems and gives its execution results.