[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Homeostasis tissue-like P systems with cell separation

  • Research
  • Published:
Acta Informatica Aims and scope Submit manuscript

Abstract

P systems are distributed, parallel computing models inspired by biology. Tissue-like P systems are an important variant of P systems, where the environment can provide objects for cells. Hence, the environment plays a critical role. Nevertheless, in actual biological tissues, there exists a peculiar biological phenomenon called “homeostasis”; that is, the internal organisms maintain stable, thereby reducing their dependence on external conditions (i.e., the environment). In this work, considering cell separation, we construct a novel variant to simulate the mechanism of biological homeostasis, called homeostasis tissue-like P systems with cell separation. In this variant, the number of object is finite, and certain substance changes occur inside the cells; moreover, an exponential workspace can be obtained with cell separation in feasible time. The computational power of this model is studied by simulating register machines, and the results show that the variant is computationally complete as number computing devices. Furthermore, to explore the computational efficiency of the model, we use the variant to solve a classic \(\textbf{NP}\)-complete problem, the SAT problem, obtaining a uniform solution with a rule length of at most 3.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Alhazov, A., Freund, R., Ivanov, S., et al.: Tissue P systems with vesicles of multisets. Int. J. Found. Comput. S. 33(3/4), 179–202 (2022)

    Article  MathSciNet  Google Scholar 

  2. Aman, B., Ciobanu, G.: Travelling salesman problem in tissue P systems with costs. J. Membr. Comput. 3(2), 97–104 (2021)

    Article  MathSciNet  Google Scholar 

  3. Andreu-Guzmán, J.A., Valencia-Cabrera, L.: A novel solution for GCP based on an OLMS membrane algorithm with dynamic operators. J. Membr. Comput. 2(1), 1–13 (2020)

    Article  MathSciNet  Google Scholar 

  4. Buiu, C., Florea, A.G.: Membrane computing models and robot controller design, current results and challenges. J. Membr. Comput. 1(4), 262–269 (2019)

    Article  MathSciNet  Google Scholar 

  5. Buño, K., Adorna, H.: Distributed computation of a k P systems with active membranes for SAT using clause completion. J. Membr. Comput. 2(2), 108–120 (2020)

    Article  MathSciNet  Google Scholar 

  6. Ciobanu, G., Pan, L., Păun, G., et al.: P systems with minimal parallelism. Theor. Comput. Sci. 378(1), 117–130 (2007)

    Article  MathSciNet  Google Scholar 

  7. Cooper, J., Nicolescu, R.: Alternative representations of P systems solutions to the graph colouring problem. J. Membr. Comput. 1(2), 112–126 (2019)

    Article  MathSciNet  Google Scholar 

  8. Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., et al.: A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theor. Comput. Sci. 404(1–2), 76–87 (2008)

    Article  MathSciNet  Google Scholar 

  9. Díaz-Pernil, D., Christinal, H.A., Gutiérrez-Naranjo, M.A.: Solving the 3-COL problem by using tissue P systems without environment and proteins on cells. Inf. Sci 430–431, 240–246 (2018)

    Article  MathSciNet  Google Scholar 

  10. Frisco, P., Govan, G., Leporati, A.: Asynchronous P systems with active membranes. Theor. Comput. Sci. 429, 74–86 (2012)

    Article  MathSciNet  Google Scholar 

  11. García-Quismondo, M., Levin, M., Lobo, D.: Modeling regenerative processes with membrane computing. Inf. Sci. 381, 229–249 (2017)

    Article  Google Scholar 

  12. García-Quismondo, M., Hintz, W.D., Schuler, M.S., et al.: Modeling diel vertical migration with membrane computing. J. Membr. Comput. 3(1), 35–50 (2021)

    Article  MathSciNet  Google Scholar 

  13. Guo, P., Quan, C., Chen, H., et al.: MEAMVC: a membrane evolutionary algorithm for solving minimum vertex cover problem. IEEE Access 7, 60774–60784 (2019)

    Article  Google Scholar 

  14. Hu, J., Peng, H., Wang, J., et al.: kNN-P: A kNN classifier optimized by P systems. Theor. Comput. Sci. 817, 55–65 (2020)

    Article  MathSciNet  Google Scholar 

  15. Leporati, A., Manzoni, L., Mauri, G., et al.: Characterising the complexity of tissue P systems with fission rules. J. Comput. Syst. Sci. 90, 115–128 (2017)

    Article  MathSciNet  Google Scholar 

  16. Luo, Y., Tan, H., Zhang, Y., et al.: The computational power of timed P systems with active membranes using promoters. Math. Struct. Comput. Sci. 29(5), 663–680 (2019)

    Article  MathSciNet  Google Scholar 

  17. Luo, Y., Zhao, Y., Chen, C.: Homeostasis tissue-like P systems. IEEE Trans. Nanobiosci. 20(1), 126–136 (2021)

    Article  Google Scholar 

  18. Luo, Y., Zhao, Y., Liu, Y.: Timed tissue P systems with channel states. IEEE Trans Nanobiosci (2023). https://doi.org/10.1109/TNB.2023.3278653

    Article  Google Scholar 

  19. Martín-Vide, C., Păun, G., Pazos, J., et al.: Tissue P systems. Theor. Comput. Sci. 296(2), 295–326 (2003)

    Article  MathSciNet  Google Scholar 

  20. Pan, L., Ishdorj, T.-O.: P systems with active membranes and separation rules. J. Univers. Comput. Sci. 10(5), 630–649 (2004)

    MathSciNet  Google Scholar 

  21. Pan, L., Pérez-Jiménez, M.J.: Computational complexity of tissue-like P systems. J. Complex. 26(3), 296–315 (2010)

    Article  MathSciNet  Google Scholar 

  22. Pan, L., Song, B., Valencia-Cabrera, L., et al.: The computational complexity of tissue P systems with evolutional symport/antiport rules. Complexity 2018, 1–21 (2018)

    Article  Google Scholar 

  23. Pan, L., Alhazov, A., Su, H., et al.: Local synchronization on asynchronous tissue P systems with symport/antiport rules. IEEE Trans. Nanobiosci. 19(2), 315–320 (2020)

    Article  Google Scholar 

  24. Păun, G.: Computing with membranes. J. Comput. Syst. Sci. 61(1), 108–143 (2000)

    Article  MathSciNet  Google Scholar 

  25. Păun, G., Rozenberg, G.: A guide to membrane computing. Theor. Comput. Sci. 287(1), 73–100 (2002)

    Article  MathSciNet  Google Scholar 

  26. Păun, G., Pérez-Jiménez, M.J., Riscos-Núñez, A.: Tissue P systems with cell division. Int. J. Comput. Commun. 3(3), 295–303 (2008)

    Article  Google Scholar 

  27. Peng, H., Wang, J.: Coupled neural P systems. IEEE Trans. Neural Networ. Learn. Syst. 30(6), 1672–1682 (2019)

    Article  MathSciNet  Google Scholar 

  28. Pérez-Jiménez, M.J., Sosík, P.: An optimal frontier of the efficiency of tissue P systems with cell separation. Fundam. Inf. 138(1–2), 45–60 (2015)

    MathSciNet  Google Scholar 

  29. Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, Verlag (1997)

    Book  Google Scholar 

  30. Singh, G., Deep, K.: Effectiveness of new multiple-PSO based membrane optimization algorithms on CEC 2014 benchmarks and Iris classification. Nat. Comput. 16(3), 473–496 (2017)

    Article  MathSciNet  Google Scholar 

  31. Song, B., Zeng, X., Jiang, M., et al.: Monodirectional tissue P systems with promoters. IEEE Trans. Cybern. 51(1), 438–450 (2020)

    Article  Google Scholar 

  32. Song, B., Li, K., Orellana-Martín, D., et al.: Cell-like P systems with evolutional symport/antiport rules and membrane creation. Inf Comput (2020). https://doi.org/10.1016/j.ic.2020.104542

    Article  MathSciNet  Google Scholar 

  33. Song, B., Zeng, X., Rodríguez-Patón, A.: Monodirectional tissue P systems with channel states. Inf. Sci. 546, 206–219 (2021)

    Article  MathSciNet  Google Scholar 

  34. Song, X., Valencia-Cabrera, L., Peng, H., et al.: Spiking neural P systems with autapses. Inf. Sci. 570, 383–402 (2021)

    Article  MathSciNet  Google Scholar 

  35. Song, B., Li, K., Orellana-Martín, D., et al.: Tissue P systems with states in cells. IEEE Trans Nanobiosci (2023). https://doi.org/10.1109/TC.2023.3257506

    Article  Google Scholar 

  36. Sosík, P., Cienciala, L.: Computational power of cell separation in tissue P systems. Inf. Sci. 279, 805–815 (2014)

    Article  MathSciNet  Google Scholar 

  37. Tamori, Y., Deng, W.: Compensatory cellular hypertrophy: the other strategy for tissue homeostasis. Trends. Cell Biol. 24(4), 230–237 (2014)

    Article  Google Scholar 

  38. Wang, J., Peng, H., Yu, W., et al.: Interval-valued fuzzy spiking neural P systems for fault diagnosis of power transmission networks. Eng. Appl. Artif. Intel. 82, 102–109 (2019)

    Article  Google Scholar 

  39. Wu, T., Zhang, L., Lyu, Q., et al.: Asynchronous spiking neural P systems with local synchronization of rules. Inf. Sci. 588, 1–12 (2022)

    Article  Google Scholar 

  40. Xue, J., Hu, J., Wang, Y., et al.: Hypergraph membrane system based \( F^2 \) fully convolutional neural network for brain tumor segmentation. Appl Soft Comput (2020). https://doi.org/10.1016/j.asoc.2020.106454

    Article  Google Scholar 

  41. Zhang, X., Zeng, X., Luo, B., et al.: A uniform solution to the independent set problem through tissue P systems with cell separation. Front. Comput. Sci. 6(4), 477–488 (2012)

    MathSciNet  Google Scholar 

  42. Zhang, G., Pérez-Jiménez, M.J., Gheorghe, M.: Real-life Applications with Membrane Computing. Springer, Verlag (2017)

    Book  Google Scholar 

Download references

Acknowledgements

This work was supported by the Natural Science Foundation of Chongqing China (CSTB2024NSCQ-MSX0225).

Author information

Authors and Affiliations

  1. College of Big Data and Intelligent Engineering, Yangtze Normal University, Chongqing, 408100, China

    Yueguo Luo & Wenqin Li

  2. Business School, Shandong Normal University, Jinan, 250014, China

    Yuzhen Zhao

  3. School of Artificial Intelligence and Big Data, Chongqing Metropolitan College of Science and Technology, Chongqing, 402167, China

    Ping Guo

Authors
  1. Yueguo Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuzhen Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wenqin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ping Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Y. Zhao. and Y. Luo. prepared conceptualization and methodology; P. Guo and W. Li prepared validation and formal analysis; Y. Luo. and Y. Zhao. wrote original draft; W. Li Prepared Figs. 1–7. All authors reviewed the manuscript.

Corresponding authors

Correspondence to Yuzhen Zhao or Ping Guo.

Ethics declarations

Conflict of interest

The authors declare no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Luo, Y., Zhao, Y., Li, W. et al. Homeostasis tissue-like P systems with cell separation. Acta Informatica 62, 3 (2025). https://doi.org/10.1007/s00236-024-00470-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00236-024-00470-y

Search

Navigation