![](/images/graphics-bg.png)
Time-Free Solution to Hamilton Path Problems Using P Systems with d-Division
Joint Authors
Zheng, Hongjiang
Song, Tao
Wang, Xun
Source
Journal of Applied Mathematics
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-09-14
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Song, Tao& Wang, Xun& Zheng, Hongjiang. 2013. Time-Free Solution to Hamilton Path Problems Using P Systems with d-Division. Journal of Applied Mathematics،Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-512877
Modern Language Association (MLA)
Song, Tao…[et al.]. Time-Free Solution to Hamilton Path Problems Using P Systems with d-Division. Journal of Applied Mathematics No. 2013 (2013), pp.1-7.
https://search.emarefa.net/detail/BIM-512877
American Medical Association (AMA)
Song, Tao& Wang, Xun& Zheng, Hongjiang. Time-Free Solution to Hamilton Path Problems Using P Systems with d-Division. Journal of Applied Mathematics. 2013. Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-512877
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-512877