[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Tissue P systems with evolutional communication rules with two objects in the left-hand side

Published: 19 October 2022 Publication History

Abstract

In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is an important task to tackle the P versus NP problem. Adding syntactic and/or semantic ingredients can mean passing from non-efficiency to presumed efficiency. Here, we try to get narrow frontiers, setting the stage to adapt efficient solutions from a family of P systems to another one. In order to do that, a solution to the SAT problem is given by means of a family of tissue P systems with evolutional symport/antiport rules and cell separation with the restriction that both the left-hand side and the right-hand side of the rules have at most two objects; that is, with recognizer P systems from TSEC(2,2). This result improves a previous one, when 3 objects could be used in the left-hand side of the evolutional communication rules

References

[1]
Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Rius-Font M (2009) Characterizing tractability by tissue–like p systems. In: Gutiérrez-Escudero R, Gutiérrez-Naranjo MA, Păun G, Pérez-Hurtado I, Riscos-Núñez A (eds) Proceedings of the 7th brainstorming week on membrane computing. Fénix Editora, Seville, pp 169–180
[2]
Ionescu M, Păun G, and Yokomori T Spiking neural P systems Fund Inform 2006 71 2–3 279-308
[3]
Leporati A, Manzoni L, Porreca AE, and Zandron C Characterising the complexity of tissue P systems with fission rules J Comput Syst Sci 2017 90 115-128
[4]
Martín-Vide C, Păun G, Pazos J, and Rodríguez-Patón A Tissue P systems Theoret Comput Sci 2003 296 2 295-326
[5]
Pan L, Song B, Valencia-Cabrera L, and Pérez-Jiménez MJ The computational complexity of tissue P systems with evolutional symport/antiport rules Complexity 2018 2018 21
[6]
Pan L, Pérez-Jiménez MJ, Riscos-Núñez A, Rius-Font M (2012) New frontiers of the efficiency in tissue P systems. In: Pre-Proceedings of the Asian conference on membrane computing (ACMC 2012), Wuhan, pp 61–73
[7]
Păun G Computing with membranes J Comput Syst Sci 2000 61 1 108-143
[8]
Pérez-Jiménez MJ (2005) An approach to computational complexity in Membrane Computing. In: Proceedings of the international workshop on membrane computing (WMC5), vol 3365. Milano, Italy, pp 85–109
[9]
Pérez-Jiménez MJ, Sosík P (2012) Improving the efficiency of tissue P systems with cell separation. In: García-Quismondo M, Macías-Ramos LF, Păun G, Pérez-Hurtado I, Valencia-Cabrera L (eds) Proceedings of the 10th brainstorming week on membrane computing, vol. 2, pp 105–140. Fénix Editora, Seville
[10]
Pérez-Jiménez MJ, Romero-Jiménez A, and Sancho-Caparrini F Complexity classes in models of cellular computing Nat Comput 2003 2 3 265-285
[11]
Porreca AE, Murphy N, Pérez-Jiménez MJ (2012) An optimal frontier of the efficiency of tissue P Systems with Cell Division. In: Martínez-del-Amor MA, Păun G, Pérez-Hurtado I, Romero-Campero FJ (eds) Proceedings of the 10th brainstorming week on membrane computing, vol 1. Fénix Editora, Seville, pp 141–166
[12]
Song B, Zhang C, and Pan L Tissue-like P systems with evolutional symport/antiport rules Inf Sci 2017 378 177-193

Index Terms

  1. Tissue P systems with evolutional communication rules with two objects in the left-hand side
              Index terms have been assigned to the content through auto-classification.

              Recommendations

              Comments

              Please enable JavaScript to view thecomments powered by Disqus.

              Information & Contributors

              Information

              Published In

              cover image Natural Computing: an international journal
              Natural Computing: an international journal  Volume 22, Issue 1
              Mar 2023
              216 pages

              Publisher

              Kluwer Academic Publishers

              United States

              Publication History

              Published: 19 October 2022
              Accepted: 13 September 2022

              Author Tags

              1. Membrane computing
              2. Symport/antiport rules
              3. The P versus NP problem
              4. SAT problem

              Qualifiers

              • Research-article

              Funding Sources

              Contributors

              Other Metrics

              Bibliometrics & Citations

              Bibliometrics

              Article Metrics

              • 0
                Total Citations
              • 0
                Total Downloads
              • Downloads (Last 12 months)0
              • Downloads (Last 6 weeks)0
              Reflects downloads up to 09 Mar 2025

              Other Metrics

              Citations

              View Options

              View options

              Figures

              Tables

              Media

              Share

              Share

              Share this Publication link

              Share on social media