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

• 영문명: Algorithm for Computing J Relations in the Monoid of Boolean Matrices
• 발행기관: 한국IT서비스학회
• 저자명: 한재일(Jae-Il Han)
• 간행물 정보: 『한국IT서비스학회지』한국IT서비스학회지 제7권 제4호, 221~230쪽, 전체 10쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2008.12.31

영문 초록

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.

키워드

Semigroup Ideal Green Relation Boolean matrix Algorithm Computational Complexity