TY  - THES
T1  - A solution to the turnpike problem in membranes
A1  - Albores, Maria Cristina
A2  - Juayong, Richelle Ann
LA  - English
UL  - https://tuklas.up.edu.ph/Record/UP-99796217608946927
AB  - P systems are massively parallel computing models that are based on the architecture of living cells; P system variants, namely the P system with active membranes and the P system with membrane creation, have been used to solve NP-complete problems in polynomial time or better by trading time for an exponential workspace. The Turnpike Problem involves the reconstruction of those point sets on a line that arise from a given distance multiset. Although the Turnpike Problem itself is of unknown complexity, variants of it have been proven to be NP-complete, and there are no existing polynomial algorithms for it. In this paper, we present a P system with active membranes and membrane creation that implements an O(2[raised to n] n log n)-time backtracking algorithm for the Turnpike Problem in linear time.
CN  - LG 993.5 2009 C65 A42
KW  - Biologically-inspired computing.
KW  - Models, Biological.
KW  - Molecular biology -- Mathematical models.
KW  - Turnpike Problem.
ER  -