효율적인 J 관계 계산을 위한 L 클래스 계산의 개선

• 영문명: Improved Computation of L-Classes for Efficient Computation of J Relations
• 발행기관: 한국IT서비스학회
• 저자명: 한재일(Jae-Il Han) 김영만(Young-Man Kim)
• 간행물 정보: 『한국IT서비스학회지』한국IT서비스학회지 제9권 제4호, 219~229쪽, 전체 11쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2010.12.30

영문 초록

The Green's equivalence relations have played a fundamental role in the development of semigroup theory. They are concerned with mutual divisibility of various kinds, and all of them reduce to the universal equivalence in a group. Boolean matrices have been successfully used in various areas, and many researches have been performed on them. Studying Green's relations on a monoid of boolean matrices will reveal important characteristics about boolean matrices, which may be useful in diverse applications. Although there are known algorithms that can compute Green relations, most of them are concerned with finding one equivalence class in a specific Green's relation and only a few algorithms have been appeared quite recently to deal with the problem of finding the whole D or J equivalence relations on the monoid of all nxn Boolean matrices. However, their results are far from satisfaction since their computational complexity is exponential-their computation requires multiplication of three Boolean matrices for each of all possible triples of nxn Boolean matrices and the size of the monoid of all nxn Boolean matrices grows exponentially as n increases. As an effort to reduce the execution time, this paper shows an isomorphism between the R relation and L relation on the monoid of all n x n Boolean matrices in terms of transposition, introduces theorems based on it, discusses an improved algorithm for the J relation computation whose design reflects those theorems and gives its execution results.

목차

1. 서 론

2. 관련 연구

3. 용어 및 기호 정의

4. J 관계 계산 알고리즘의 개선

5. 계산 복잡도 및 실행 결과

6. 결 론

키워드

Isomorphism Boolean Matrix Semigroup Monoid Ideal Green's Relation Algorithm Computational Complexity