Linearizability of n-linear Sirups

HÉCTOR J. HERNÁNDEZ, DONGXING TANG

Resumen


A LINEAR PROGRAM IS EASIER TO EVALUATE THAN A NONLINEAR PROGRAM. HENCE, GIVEN A RECURSIVE PROGRAM, IT IS DESIABLE TO FIND AN EQUIVALENT LINAER PROGRAM. HOWEVER, NOT ALL NONLINEAR PROGRAMS ARE LINEARIZABLE. THEORETICALLY, AN M - LINEAR PROGRAM IS EASIER TO EVALUTE THA AN NO - LINEAR PROGRAM WHE M < N, SINCE THE DERIVATION TREE OF THE FORMER ONE IS OF SMALLER ARITY THAN THE DERIVATION TREE OF THE LATER. THUS, WHE AN N- LINEAR PROGRAM IS NOT LINEALIRIZABLE, WE WOULD LIKE TO FIND ANOTHER EQUIVALENT M - LINEAR PROGRAM WITH M < N. IN THIS PAPER, WE CONSIDER TWO POSSIBILITIES OF 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 OF DETERMINING WHETHER AN N - LINEAR SIRUP IS EQUIVALENT TO ITS DERIVATIVE OR TO ITS GENERAL ZYT - LINEARIZATION IS NP - HARD. WE THENN GIVE A TIGHTER CONDITION WHICH IS NECESSARY AND SUFFICIENT FOR TESTING THOSE EQUIVALENCES. THE OTHER POSSIBILITY IS TO CONSIDER THE EQUIVALENCE BETWEEN AN N - LINEAR STRUP AND ANOTHER M - LINEAR PROGRAM, M < N =M. WE ALSO PROVE THAT THE PROBLEM OF DETERMINIG WHETHER AN N - LINEAR SIRUP IS EQUIVALENT TO ITS K - ZYT - LINEARIZATION IS NP - HARD. THEN, WE PRESENT A THIGHTER, EXACT CONDITION FOR TESTING WHETHER AN N - LINEAR SIRUP IS EQUIVALENT TO ITS K - ZYT - LINEARIZATION. WE DO NOT KNOW WHETHER TESTING ANY OF THE ABOVE EQUIVALENCES IS DECIDABLE.

Palabras clave


DEDUCTIBLE DATABASES; OPTIMIZATION; DATALONG PROGRAMS; LINEARIZATION; SIRUP (SINGLE RECURSIVE PROGRAMS)

Texto completo:

pdf


Contacto:
Oscar Zavala