효율적인 J 관계 계산을 위한 L 클래스 계산의 개선 = Improved Computation of L-Classes for Efficient Computation of J Relations

다국어 초록 (Multilingual Abstract)

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.

목차 (Table of Contents)

• 1. 서 론
• 2. 관련 연구
• 3. 용어 및 기호 정의
• 4. J 관계 계산 알고리즘의 개선
• 5. 계산 복잡도 및 실행 결과
• 6. 결 론

참고문헌 (Reference)

1 한재일, "효율적인 D-클래스 계산을 위한 알고리즘" 한국IT서비스학회 6 (6): 151-158, 2007

2 한재일, "불리언 행렬의 모노이드에서의 J 관계 계산 알고리즘" 한국IT서비스학회 7 (7): 221-230, 2008

3 한재일, "모든 l x n, n x m, m x k 불리언 행렬 사이의 중첩곱셈에 대한 연구" 한국IT서비스학회 5 (5): 191-198, 2006

4 Angluin, D., "The four Russians’ algorithm for boolean matrix multiplication is optimal in its class" 8 (8): 29-33, 1976

5 Pratt, V. R., "The Power of Negative Thinking in Multiplying Boolean matrices" 80-83, 1974

6 Straubing, H., "The Burnside problem for semigroups of matrices. in: Combinatorics on Words, Progress and Perspectives" Academic Press 279-295, 1983

7 Rim, D. S., "Tables of DClasses in the semigroup B of the binary relations on a set X with n-elements" 20 (20): 9-13, 1983

8 Lallement, G., "Semigroups and Combinatorial Applications" John Wiley and Sons 1979

9 Heyworth, A., "One-Sided Noncommutative Grobner Bases with Applications to Computing Green’s Relations" 242 : 401-416, 2001

10 Plemmons, R. J., "On the semigroup of binary relations" 35 : 743-753, 1970

11 Atkinson, D. M., "On the integer complexity of Boolean matrix multiplication" 18 (18): 53-, 1986

12 Lallement, G., "On the determination of Green’s relations in finite transformation semigroups" 10 : 481-498, 1990

13 Simon, I., "On semigroups of matrices over the tropical semiring" 28 : 277-294, 1994

14 Wall, J. R., "Green’s relations for stochastic matrices" 25 (25): 247-260, 1975

15 Konieczny, J., "Green’s equivalences in finite semigroups of binary relations" 48 : 235-252, 1994

16 Sutner, K., "Finite State Machines and Syntatic Semigroups" 2 : 78-87, 1991

17 Lee, L., "Fast context-free grammar parsing require fast Boolean matrix multiplication" 49 (49): 1-15, 2002

18 Yi, X., "Fast Encryption for Multimedia" 47 (47): 101-107, 2001

19 Linton, S. A., "Computing Transformation Semigroups" 33 : 145-162, 2002

20 김창범, "Classifications of D-classes in the semigroup Mn(F) of all nxn Boolean matrices over F = {0, 1}" 16 (16): 338-348, 2006

21 Booth, K. S., "Boolean matrix multiplication using only bit operations" 9 (9): 23-, 1977

22 Howie, J. M., "An Introduction to semigroup theory" Oxford University Press 1995

23 Froidure, V., "Algorithms for computing finite semigroups" 112-126, 1997

24 Champarnaud, J. M., "AUTOMATE, a computing package for automata and finite semigroups" 12 : 197-220, 1991

25 Cousineau, G., "APL programs for direct computation of a finite semigroup" 73 : 67-74, 1973

26 Nakamura, Y., "A partitioning- based logic optimization method for large scale circuits with Boolean matrx" 653-657, 1995

27 Comstock, D. R., "A note on multiplying Boolean matrices II" 7 (7): 13-, 1964

28 Yelowitz, L., "A Note on the Transitive Closure of a Boolean Matrix" 25 (25): 30-, 1978

29 Macii, E., "A Discussion of Explicit Methods for Transitive Closure Computation Based on Matrix Multiplication" 799-801, 1995

30 Martin, D. F., "A Boolean matrix method for the computation of linear precedence functions" 15 (15): 448-454, 1972