Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-24T00:22:17.925Z Has data issue: false hasContentIssue false
  • English
  • Français

A time-free uniform solution to subset sum problem by tissue P systems with cell division

Published online by Cambridge University Press:  27 February 2015

BOSHENG SONG ,
TAO SONG  and
LINQIANG PAN Open the ORCID record for LINQIANG PAN [Opens in a new window]
BOSHENG SONG
Affiliation:
Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China Email: [email protected] Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
TAO SONG
Affiliation:
Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China Email: [email protected]
LINQIANG PAN
Affiliation:
Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Tissue P systems are a class of bio-inspired computing models motivated by biochemical interactions between cells in a tissue-like arrangement. Tissue P systems with cell division offer a theoretical device to generate an exponentially growing structure in order to solve computationally hard problems efficiently with the assumption that there exists a global clock to mark the time for the system, the execution of each rule is completed in exactly one time unit. Actually, the execution time of different biochemical reactions in cells depends on many uncertain factors. In this work, with this biological inspiration, we remove the restriction on the execution time of each rule, and the computational efficiency of tissue P systems with cell division is investigated. Specifically, we solve subset sum problem by tissue P systems with cell division in a time-free manner in the sense that the correctness of the solution to the problem does not depend on the execution time of the involved rules.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Issue 1 , January 2017 , pp. 17 - 32
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alhazov, A., Freund, R. and Oswald, M. (2005) Tissue P systems with antiport rules and small numbers of symbols and cells. In: Developments in Language Theory. Lecture Notes in Computer Science 3572 100–111.Google Scholar
Alhazov, A., Freund, R., Leporati, A., Oswald, M. and Zandron, C. (2006) (Tissue) P systems with unit rules and energy assigned to membranes. Fundamenta Informaticae 74 (4) 391–408.Google Scholar
Bernardini, F. and Gheorghe, M. (2005) Cell communication in tissue P systems: Universality results. Soft Computing 9 (9) 640–649.Google Scholar
Cavaliere, M. and Sburlan, D. (2005) Time–independent P systems. In: Membrane Computing. Lecture Notes in Computer Science 3365 239–258.CrossRefGoogle Scholar
Díaz-Pernil, D., Pérez-Jiménez, M. J., Riscos-Núñez, A. and Romero-Jiménez, Á. (2008a) Computational efficiency of cellular division in tissue-like membrane systems. Romanian Journal of Information Science and Technology 11 (3) 229–241.Google Scholar
Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2007a) Solving subset sum in linear time by using tissue P systems with cell division. In: Bio-inspired Modeling of Cognitive Tasks. Lecture Notes in Computer Science 4527 170–179.CrossRefGoogle Scholar
Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2007b) A linear–time tissue P system based solution for the 3-coloring problem. Electronic Notes in Theoretical Computer Science 171 (2) 81–93.CrossRefGoogle Scholar
Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2008b) A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science 404 (1) 76–87.CrossRefGoogle Scholar
Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2009) Solving the independent set problem by using tissue-like P systems with cell division. In: Methods and Models in Artificial and Natural Computation. A Homage to Professor Mira's Scientific Legacy. Lecture Notes in Computer Science 5601 213–222.CrossRefGoogle Scholar
Freund, R., Păun, G. and Pérez-Jiménez, M. J. (2005) Tissue P systems with channel states. Theoretical Computer Science 330 (1) 101–116.CrossRefGoogle Scholar
Gheorghe, M., Păun, G., Pérez-Jiménez, M. J. and Rozenberg, G. (2013) Research frontiers of membrane computing: Open problems and research topics. International Journal of Foundations of Computer Science 24 (5) 547–623.Google Scholar
Ionescu, M., Păun, G. and Yokomori, T. (2006) Spiking neural P systems. Fundamenta informaticae 71 (2) 279–308.Google Scholar
Martín-Vide, C., Pazos, J., Păun, G. and Rodríguez-Patón, A. (2002) A new class of symbolic abstract neural nets: Tissue P systems. In: Computing and Combinatorics. Springer-Verlag Lecture Notes in Computer Science 2387 290–299.Google Scholar
Martín-Vide, C., Pazos, J., Păun, G. and Rodríguez-Patón, A. (2003) Tissue P systems. Theoretical Computer Science 296 (2) 295–326.Google Scholar
Pan, L. and Pérez-Jiménez, M. J. (2010) Computational complexity of tissue-like P systems. Journal of Complexity 26 (3) 296–315.Google Scholar
Pan, L., Zeng, X. and Zhang, X. (2011) Time-free spiking neural P systems. Neural Computation 23 (5) 1320–1342.CrossRefGoogle ScholarPubMed
Păun, A. and Păun, G. (2002) The power of communication: P systems with symport/antiport. New Generation Computing 20 (3) 295–305.CrossRefGoogle Scholar
Păun, G. (2000) Computing with membranes. Journal of Computer and System Sciences 61 (1) 108–143.CrossRefGoogle Scholar
Păun, G. (2002) Membrane Computing: An Introduction, Springer-Verlag.Google Scholar
Păun, G., Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2008) Tissue P systems with cell division. International Journal of Computers, Communications and Control 3 (3) 295–303.Google Scholar
Păun, G., Rozenberg, G. and Salomaa, A. (eds.) (2010) Handbook of Membrane Computing, Oxford University Press.Google Scholar
Pérez-Jiménez, M. J., Romero-Jiménez, A. and Sancho-Caparrini, F. (2006) A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics 11 (4) 423–434.Google Scholar
Salomaa, A. and Rozenberg, G. (eds.) (1997) Handbook of Formal Languages, Springer-Verlag, Berlin.Google Scholar
Song, T., Macías-Ramos, L. F., Pan, L. and Pérez-Jiménez, M. J. (2014a) Time-free solution to sat problem using P systems with active membranes. Theoretical Computer Science 529 61–68.Google Scholar
Song, T., Luo, L., He, J., Chen, Z. and Zhang, K. (2014b) Solving subset sum problems by time-free spiking neural P systems. Applied Mathematics and Information Sciences 8 (1) 327–332.CrossRefGoogle Scholar