Linearizability of n-linear Sirups

Linearizability of n-linear Sirups

dc.contributoren-US
dc.contributores-ES
dc.creatorHERNÁNDEZ, HÉCTOR J.
dc.creatorTANG, DONGXING
dc.date2009-10-05
dc.date.accessioned2018-03-16T14:22:10Z
dc.date.available2018-03-16T14:22:10Z
dc.identifierhttp://ojs.unam.mx/index.php/cys/article/view/2443
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1190316
dc.descriptionA 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.en-US
dc.descriptionA 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.es-ES
dc.formatapplication/pdf
dc.languagespa
dc.publisherComputación y Sistemases-ES
dc.relationhttp://ojs.unam.mx/index.php/cys/article/view/2443/2005
dc.sourceComputación y Sistemas; Vol 2, No 001 (1998)es-ES
dc.source1405-5546
dc.subjectDEDUCTIBLE DATABASES; OPTIMIZATION; DATALONG PROGRAMS; LINEARIZATION; SIRUP (SINGLE RECURSIVE PROGRAMS)en-US
dc.subjectes-ES
dc.titleLinearizability of n-linear Sirupsen-US
dc.titleLinearizability of n-linear Sirupses-ES
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución