Por favor, use este identificador para citar o enlazar este ítem:
http://repositoriodigital.ipn.mx/handle/123456789/15187
Título : | Linearizability of n-linear Sirups |
Autor : | Hernández, Héctor J. Tang, Dongxing |
Palabras clave : | Keywords: deductive databases, optimization, datalog programs, linearization, sirups (single recursive prograrns) |
Fecha de publicación : | 17-sep-1998 |
Editorial : | Revista Computación y Sistemas; Vol. 2 No. 1 |
Citación : | Revista Computación y Sistemas; Vol. 2 No. 1 |
Citación : | Revista Computación y Sistemas;Vol. 2 No. 1 |
Resumen : | Abstract A linear program is easier to evaluate than a nonlinear programo Hence, given a recursive program, it is desirable to find an equivalent linear programo However, not all nonlinear programs are linearizable. Theoretically, an m-linear program is easier to evaluate than an nlinear program when m < n, since the derivation tree 01 the lormer one is 01 smaller arity than the derivation tree 01 the latter. Thus, when an n-linear program is not linearizable, we would like to find another, equivalent m-linear program with m < n. In this paper, we consider two possibilities 01 linearizing n-linear sirups. First, we consider the equivalence between an n-linear sirup and its derivative or its general ZYT-linearization, which are linear programs. We show that the problem 01 determining whether an n-linear sirup 1.S equivalent to its derivatíve or to its general ZYT-linearization 1.S NP-hard. We then give a tighter condition which 1.S necessary and sufficient lor testing those equivalen ces. The other possibility is to consider the equivalence between an n-linear sirup and another m-linear program, m < n, called its k-ZYTlinearization, where k = n-m. We also prove that the problem 01 determining whether an n-linear sirup is equivalent to its k -ZYT -linearization is NP-hard. Then, we present a tighter, exact condition lor testing whether an n-linear sirup is equívalent to its k-ZYTlinearization. We do not know whether testing any 01 the above equivalences is decidable. |
URI : | http://www.repositoriodigital.ipn.mx/handle/123456789/15187 |
ISSN : | 1405-5546 |
Aparece en las colecciones: | Revistas |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
ART 3 (2).pdf | 910.76 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.