http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
강지훈(Ji-Hoon Kang),홍기영(Ki-Hyung Hong),황규영(Kyu-Young Whang),조정완(Jung-Wan Cho) 한국정보과학회 1998 정보과학회논문지(B) Vol.25 No.10
이중선형 프로그램(bilinear program)의 우선형우선(RLF) 선형화를 위한 새로운 충분조건을 제시한다. 제시하는 조건의 검사는 논리곱 질의 포함관계 검사 방법을 이용하여 지수 시간에 가능하다. 일반적인 비선형 프로그램의 선형화는 결정 불가능한 문제로 알려져 있으며, 지금까지의 선형화 연구는 대상이 되는 비선형 프로그램을 제한하여 이루어졌다. 잘 알려진 ZYT-선형화는 단 하나의 이중선형규칙만을 가진 이중선형 프로그램을 대상으로 한다. 이 논문에서는, 균일동등 (uniform equivalence) 개념을 이용한 ZYT-선형화에 관한 연구를 확장하여, 다수의 이중선형 및 선형규칙을 가진 보다 일반적인 이중선형 프로그램을 대상으로 하는 RLF-선형화를 위한 충분조건을 제시한다. 또한, RLF-선형화에 관한 이전의 연구에서 다루지 못하였던 다수의 외연 서브골을 가진 순환규칙을 허용함으로써, 지금까지의 선형화 연구에서 제안되었던 어떠한 검사 가능한 조건에 비하여도 그 대상이 넓은 조건을 제시하였다. We present new sufficient conditions for RLF (right-linear-first) linearization, which deals with bilinear datalog programs having multiple bilinear rules and multiple linear rules. The test of the conditions can be done in exponential time, by using an algorithm for checking conjunctive query containment. In general, linearization of general nonlinear programs is known as undecidable. All the previous studies on linearization have been done for some specific classes of nonlinear programs. ZYT-linearization is a well-known linearization for very simple nonlinear programs that consist of only one bilinear rule and one exit rule. The target program class of RLF-linearization is broader than that of ZYT-linearization. In this paper, we generalize a sufficient condition for ZYT-linearization that is developed by using the concept of uniform equivalence. While all the previous conditions developed on RLF-linearization can handle only those recursive rules having zero or one extensional database subgoal, the conditions presented in this paper allows recursive rules with more than one extensional database subgoal.