Top

Natural Computing

Published in:

16-12-2022

On the power of membrane dissolution in polarizationless P systems with active membranes

Authors: Zsolt Gazdag, Károly Hajagos

Published in: Natural Computing | Issue 1/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

It is known that dissolution rules are necessary in polarizationless P systems with active membranes to solve problems beyond \(\mathbf {AC^0}\) using reasonable tight uniformity conditions (Murphy and Woods, Fundam Inf Series 134:129–152, 2014). On the other hand, no solutions of such problems exist using only dissolution rules. In this paper, we show that the \(\mathbf {NL}\)-complete reachability problem can be solved in polynomial time by polarizationless P systems with active membranes using only dissolution rules under a suitable uniformity condition.

previous article Estimation of minimum viable population for giant panda ecosystems with membrane computing models

next article Face illumination normalization based on generative adversarial network

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Alhazov A, Martín-Vide C, Pan L (2003) Solving a \(\rm PSPACE\)-complete problem by P systems with restricted active membranes. Fundam Inf Series 58:67–77MATH

Alhazov A, Pérez-Jiménez MJ (2007) Uniform solution of QSAT using polarizationless active membranes. In: International conference on machines, computations and universality, pp 122-133

Gazdag Z, Hajagos K, Iván Sz (2021) On the power of P systems with active membranes using weak non-elementary membrane division. J Membr Comput 3:258–269

Gazdag Z, Gutiérrez-Naranjo MA (2014) Solving the ST-connectivity problem with pure membrane computing techniques. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Sosík, P., Zandron, C. (Eds.) Membrane Computing: 15th International Conference, LNCS vol. 8961, pp 215–228

Gazdag Z, Kolonits G (2019) A new method to simulate restricted variants of polarizationless P systems with active membranes. J Membr Comput 1(4):251–261

Gensler HJ (2002) Introduction to Logic. Routledge, LondonCrossRefMATH

Gutierrez-Naranjo MA, Perez-Jimenez MJ, Riscos-Núñez A, Romero-Campero FJ (2006) On the power of dissolution in P systems with active membranes. In: Freund, R., Păun, Gh., Rozenberg, G., Salomaa, A. (Eds.) Membrane computing: 6th international workshop, LNCS vol. 3850, pp 224–240

Jones ND (1975) Space-bounded reducibility among combinatorial problems. J Comput Syst Sci 11(1):68–85MathSciNetCrossRefMATH

Krishna SN, Rama R (1999) A variant of P systems with active membranes: solving NP-complete problems. Roman J Inf Sci Technol 2(4):357–367

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C (2014) Simulating elementary active membranes, with an application to the P conjecture. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sosík, C. Zandron (Eds.) Membrane Computing – 15th international conference, CMC15, LNCS vol. 8961, pp 284–299

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C (2017) Solving a special case of the P conjecture using dependency graphs with dissolution. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Zandron, C. (Eds.) Membrane Computing: 18th international conference, LNCS vol. 10725, pp 196-213

Murphy N, Woods D (2007) Active membrane systems without charges and using only symmetric elementary division characterise P. In: Eleftherakis, G., Kefalas, P., Păun, Gh., Rozenberg, G., Salomaa, A. (Eds.) Membrane Computing: 8th international workshop, LNCS vol. 4860, pp 367–384

Murphy N, Woods D (2008) A characterisation of NL using membrane systems without charges and dissolution. In: Calude, C.S., da Costa, J.F.G., Freund, R., Oswald, M., Rozenberg, G. (Eds.) Unconventional Computing: 7th International Conference, LNCS vol. 5204, pp 164–176

Murphy N, Woods D (2009) On acceptance conditions for membrane systems: characterisations of \(\mathbf{L}\) and \(\mathbf{NL}\). In Neary, T., Woods, D., Seda, T., Murphy, N., (Eds)., Proceedings of the international workshop on the complexity of simple programs, Cork, Ireland, Vol. 1 of Electronic proceedings in theoretical computer science., Open Publishing Association, pp 172–184

Murphy N, Woods D (2014) Uniformity is weaker than semi-uniformity for some membrane systems. Fundam Inf Series 134(1–2):129–152MathSciNetMATH

Orellana-Martín D, Riscos-Núnez A (2020) Seeking computational efficiency boundaries: the Păun’s conjecture. J Membr Comput 2:323–331MathSciNetCrossRefMATH

Păun Gh (2001) P systems with active membranes: attacking NP-complete problems. J Automata, Lang Comb Series 6(1):75–90MathSciNetMATH

Păun Gh (2005) Further twenty six open problems in membrane computing. In: Third brainstorming week on membrane computing, pp. 249–262. Fénix Editora, Sevilla

Păun Gh, Rozenberg G, Salomaa A (eds) (2010) The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, EnglandMATH

Pérez-Jiménez MJ, Romero-Jiménez Á, Sancho-Caparrini F (2006) A polynomial complexity class in P systems using membrane division. J Autom Lang Comb 11(4):423–434MathSciNetMATH

Salomaa A (1973) Formal Languages. Academic Press, New York, LondonMATH

Sosík P (2003) The computational power of cell division in P systems. Natural Computing series 2(3):287–298CrossRefMATH

Sosík P (2019) P systems attacking hard problems beyond NP: a survey. J Membr Comput 1:198–208MathSciNetCrossRefMATH

Sosík P, Rodríguez-Patón A (2007) Membrane computing and complexity theory: a characterization of PSPACE. J Comput Syst Sci Series 73(1):137–152

Woods D, Murphy N, Pérez-Jiménez MJ, Riscos-Núnez A (2009) Membrane dissolution and division in P. In: Calude, C.S., da Costa, J.F.G., Dershowitz, N., Freire, E., Rozenberg, G. (Eds.) Unconventional Computation: 8th international conference, LNCS vol. 5715, pp 262–276

Zandron C, Ferretti C, Mauri G (2001) Solving NP-complete problems using P systems with active membranes. In: Unconventional models of computation, UMC’2K: Proceedings of the Second international conference on unconventional models of computation. Springer London, London, pp 289–301

Title: On the power of membrane dissolution in polarizationless P systems with active membranes
Authors: Zsolt Gazdag
Károly Hajagos
Publication date: 16-12-2022
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 1/2023
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-022-09926-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2023

A tutorial on the formal framework for spiking neural P systems

Bio-inspired modelling as a practical tool to manage giant panda population dynamics in captivity

Automatic design of arithmetic operation spiking neural P systems

Face illumination normalization based on generative adversarial network

Preface

GPU simulations of spiking neural P systems on modern web browsers

Premium Partner