Journal
SCIENCE CHINA-INFORMATION SCIENCES
Volume 54, Issue 2, Pages 293-304Publisher
SCIENCE PRESS
DOI: 10.1007/s11432-010-4162-y
Keywords
membrane computing; tissue P system; cell separation; partition problem
Funding
- National Natural Science Foundation of China [61033003, 30870826, 60703047, 60772122, 61003038]
- Ph.D Programs Foundation of Ministry of Education of China [20100142110072]
- Fundamental Research Funds for the Central Universities [2010ZD001]
- Natural Science Foundation of Hubei Province [2008CDB113, 2008CDB180]
- Scientific Research Foundation for Doctor of Anhui University [02203104]
Ask authors/readers for more resources
Tissue P systems are distributed parallel and non-deterministic computing models in the framework of membrane computing, which are inspired by intercellular communication and cooperation between neurons. Recently, cell separation is introduced into tissue P systems, which enables systems to generate an exponential workspace in a polynomial time. In this work, the computational power of tissue P systems with cell separation is investigated. Specifically, a uniform family of tissue P systems with cell separation is constructed for efficiently solving a well-known NP-complete problem, the partition problem.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available