| 한글제목(Korean Title) |
균일 동등을 이용한 RLF-선형화 가능성의 일반화 |
| 영문제목(English Title) |
Generalization of RLF-linearizability based on Uniform Equivalence |
| 저자(Author) |
강지훈
홍기영
황규영
조정완
Ji-Hoon Kang
Ki-Hyung Hong
Kyu-Young Whang
Jung-Wan Cho
|
| 원문수록처(Citation) |
VOL 25 NO. 10 PP. 1478 ~ 1492 (1998. 10) |
한글내용
(Korean Abstract) |
이중선형 프로그램(bilinear program)의 우선형우선(RLF) 선형화를 위한 새로운 충분조건을 제시한다. 제시하는 조건의 검사는 논리곱 질의 포함관계 검사 방법을 이용하여 지수 시간에 가능하다. 일반적인 비선형 프로그램의 선형화는 결정 불가능한 문제로 알려져 있으며, 지금까지의 선형화 연구는 대상이 되는 비선형 프로그램을 제한하여 이루어졌다. 잘 알려진 ZYT-선형화는 단 하나의 이중선형규칙만을 가진 이중선형 프로그램을 대상으로 한다. 이 논문에서는, 균일동등 (uniform equivalence) 개념을 이용한 ZYT-선형화에 관한 연구를 확장하여, 다수의 이중선형 및 선형규칙을 가진 보다 일반적인 이중선형 프로그램을 대상으로 하는 RLF-선형화를 위한 충분조건을 제시한다. 또한, RLF-선형화에 관한 이전의 연구에서 다루지 못하였던 다수의 외연 서브골을 가진 순환규칙을 허용함으로써, 지금까지의 선형화 연구에서 제안되었던 어떠한 검사 가능한 조건에 비하여도 그 대상이 넓은 조건을 제시하였다.
|
영문내용
(English Abstract) |
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. |
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
