Time-Free Solution to Hamilton Path Problems Using P Systems with d -Division

Tao Song, Xun Wang and Hongjiang Zheng

Journal of Applied Mathematics, 2013, vol. 2013, 1-7

Abstract:

P systems with d -division are a particular class of distributed and parallel computing models investigated in membrane computing, which are inspired from the budding behavior of Baker’s yeast (a cell can generate several cells in one reproducing cycle). In previous works, such systems can theoretically generate exponential working space in linear time and thus provide a way to solve computational hard problems in polynomial time by a space-time tradeoff, where the precise execution time of each evolution rule, one time unit, plays a crucial role. However, the restriction that each rule has a precise same execution time does not coincide with the biological fact, since the execution time of biochemical reactions can vary because of external uncontrollable conditions. In this work, we consider timed P systems with d -division by adding a time mapping to the rules to specify the execution time for each rule, as well as the efficiency of the systems. As a result, a time-free solution to Hamiltonian path problem ( HPP ) is obtained by a family of such systems (constructed in a uniform way), that is, the execution time of the rules (specified by different time mappings) has no influence on the correctness of the solution.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/JAM/2013/975798.pdf (application/pdf)
http://downloads.hindawi.com/journals/JAM/2013/975798.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnljam:975798

DOI: 10.1155/2013/975798

Access Statistics for this article

More articles in Journal of Applied Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().