본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

모든 $l{\times}n,\;n{\times}m,\;m{\times}k$ 불리언 행렬 사이의 중첩곱셈에 대한 연구
A Study on the Two Consecutive Multiplications of All $l{\times}n,\;n{\times}m\;and\;m{\times}k$ Boolean Matrices

한재일   (국민대학교 컴퓨터학부UU0000250  );
  • 초록

    Boolean matrices have been successfully used in various areas, and many researches have been performed on them. However, almost all the researches focus on the efficient multiplication of two boolean matrices and no research has been shown to deal with the multiplication of all boolean matrices and their consecutive multiplications. The paper suggests a mathematical theory that enables the efficient consecutive multiplications of all $l{\times}n,\;n{\times}m,\;and\;m{\times}k$ boolean matrices, and discusses its computational complexity and the execution results of the consecutive multiplication algorithm based on the theory.


  • 주제어

    Boolean Matrix .   Space Complexity .   Time Complexity .   NP-complete.  

  • 참고문헌 (15)

    1. 신철규, 한재일, '내부 순환문 개선을 통한 Linux 기반의 D-클래스 계산 고효율 순차 알고리즘', 한국SI학회 춘계학술대회 논문집, (2005), pp.526-531 
    2. Comstock, D. R., 'A note on multiplying Boolean matrices II', CACM, Vol.7, No.1 (1964), p.13 
    3. Yelowitz, L., 'A Note on the Transitive Closure of a Boolean Matrix', ACM SIGMOD Record, Vol.25, No.2(1978), p.30 
    4. Booth, K. S., 'Boolean matrix multiplication using only O (n log 2 7 log n ) bit operations', ACM SIGACT News, Vol.9, No.3(1977), p.23 
    5. Nakamura, Y. and T. Yoshimura, 'A partitioning- based logic optimization method for large scale circuits with Boolean matrx', Proceedings of the 32nd ACM/IEEE conference on Design automation, (1995), pp. 653-657 
    6. 신철규, 한재일, '공유 메모리 기반의 고성능 D-클래스 계산 병렬 알고리즘', 한국컴퓨터 종합학술대회 논문집, 제32권, 제1호(2005), pp.10-12 
    7. Martin, D. F., 'A Boolean matrix method for the computation of linear precedence functions', CACM, Vol.15, No.6(1972), pp. 448-454 
    8. 신철규, 한재일, '그리드 컴퓨팅 환경에서의 D-클래스 계산 병렬 알고리즘', 한국정보처 리학회 춘계학술대회 논문집, 제12권, 제1호 (2005), pp.929-932 
    9. Lee, L., 'Fast context-free grammar parsing require fast Boolean matrix multiplication', JACM, Vol.49, No.1(2002), pp. 1-15 
    10. Yi, X. et al., 'Fast Encryption for Multimedia', IEEE Transactions on Consumer Electronics, Vol.47, No.1(2001), pp.101-107 
    11. Pratt, V. R., 'The Power of Negative Thinking in Multiplying Boolean matrices', Proceedigs of the annual ACM symposium on Theory of computing, (1974), pp.80-83 
    12. Atkinson, D. M., N. Santoro, and J. Urrutia, 'On the integer complexity of Boolean matrix multiplication', ACM SIGACT News, Vol.18, No.1(1986), p.53 
    13. Rim, D. S. and J. B. Kim, 'Tables of DClasses in the semigroup B of the binary relations on a set X with n-elements', Bull. Korea Math. Soc., Vol.20, No.1(1983), pp. 9-13 
    14. Angluin, D., 'The four Russians' algorithm for boolean matrix multiplication is optimal in its class', ACM SIGACT News, Vol.8, No.1(1976), pp.29-33 
    15. Macii, E., 'A Discussion of Explicit Methods for Transitive Closure Computation Based on Matrix Multiplication', 29th Asilom Conference on Signals, Systems and Computers, Vol.2(1995), pp.799-801 
  • 이 논문을 인용한 문헌 (3)

    1. Han, Jae-Il 2007. "Algorithm for Efficient D-Class Computation" 한국IT서비스학회지 = Journal of Information Technology Services, 6(1): 151~158     
    2. Han, Jae-Il 2008. "Algorithm for Computing J Relations in the Monoid of Boolean Matrices" 한국IT서비스학회지 = Journal of Information Technology Services, 7(4): 221~230     
    3. Han, Jae-Il ; Kim, Young-Man 2010. "Improved Computation of L-Classes for Efficient Computation of J Relations" 한국IT서비스학회지 = Journal of Information Technology Services, 9(4): 219~229     

 저자의 다른 논문

  • 한재일 (15)

    1. 2004 "Java 기반의 D-클래스 계산 패키지 구현에 대한 연구" 한국SI학회지 = Journal of the Korea society of system integration 3 (2): 99~104    
    2. 2005 "웹기반 학생상담시스템에 대한 연구" 한국SI학회지 = Journal of the Korea society of system integration 4 (1): 141~148    
    3. 2005 "전자거버넌스 시스템의 구조에 대한 연구" 한국콘텐츠학회논문지 = The Journal of the Korea Contents Association 5 (1): 209~215    
    4. 2006 "모든 m$\times$k 불리언 행렬과의 효율적 곱셈에 관한 연구" 한국콘텐츠학회논문지 = The Journal of the Korea Contents Association 6 (2): 27~33    
    5. 2007 "센서 미들웨어 기술" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 25 (12): 35~48    
    6. 2007 "효율적인 D-클래스 계산을 위한 알고리즘" 한국IT서비스학회지 = Journal of Information Technology Services 6 (1): 151~158    
    7. 2007 "D-클래스 계산을 위한 불리언 행렬의 효율적 곱셈 및 알고리즘" 한국산업정보학회논문지 = Journal of the Korea Industrial Information Systems Research 12 (2): 68~78    
    8. 2008 "불리언 행렬의 모노이드에서의 J 관계 계산 알고리즘" 한국IT서비스학회지 = Journal of Information Technology Services 7 (4): 221~230    
    9. 2009 "질의의 지역성을 이용한 효율적인 하이브리드 검색 서비스" 한국IT서비스학회지 = Journal of Information Technology Services 8 (3): 171~184    
    10. 2010 "효율적인 J 관계 계산을 위한 L 클래스 계산의 개선" 한국IT서비스학회지 = Journal of Information Technology Services 9 (4): 219~229    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드
  • 원문이 없습니다.

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기