Top

Soft Computing

Published in:

19-06-2018 | Foundations

A uniform solution to SAT problem by symport/antiport P systems with channel states and membrane division

Authors: Suxia Jiang, Yanfeng Wang, Yansen Su

Published in: Soft Computing | Issue 12/2019

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

search-config

AI-assisted search

Off

Abstract

Cell-like P systems with channel states and symport/antiport rules are distributed parallel computing devices, where a state associated with each channel is used to control communication between neighboring regions. In this work, membrane division is introduced into cell-like P systems with channel states and symport/antiport rules, and we call this variant of cell-like P systems as symport/antiport P systems with channel states and membrane division. The computational efficiency of such kind of P systems is investigated. We provide a uniform solution to the SAT problem by cell-like P systems with channel states using membrane division and symport/antiport rules of length at most 2, where the P system can solve all instances of the problem with the same size.

next article Structures of compactly generated lattices described by cut sets of L-valued sets

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 "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

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

Alhazov A, Freund R (2005) P systems with one membrane and symport/antiport rules of five symbols are computationally complete. In: Proceedings of the Third Brainstorming Week on Membrane Computing. Sevilla, pp 20–28

Alhazov A, Rogozhin Y (2006) Towards a characterization of P systems with minimal symport/antiport and two membranes. Lect Notes Comput Sci 436(1):135–153MATHCrossRef

Bernardini F, Gheorghe M (2003) On the power of minimal symport/antiport. In: Proceedings of the 3rd Workshop on Membrane Computing. pp 72–83

Csuhaj-Varjú E, Margenstern M, Vaszil G, Verlan S (2007) On small universal antiport P systems. Theor Comput Sci 372:152–164MathSciNetMATHCrossRef

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

Díaz-Pernil D, Gutierrez-Naranjo MA, Pérez-Jiménez MJ et al (2009) Solving the independent set problem by using tissue-like P systems with cell division. Lect Notes Comput Sci 5601:213–222CrossRef

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

Freund R, Oswald M (2003a) P systems with activated/prohibited membrane channels. Lect Notes Comput Sci 2597:261–269MathSciNetMATHCrossRef

Freund R, Păun Gh, Pérez-Jiménezc MJ (2005) Tissue P systems with channel states. Theor Comput Sci 330(1):101–116MathSciNetMATHCrossRef

Garey MR, Johnson DJ (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman and Company, New YorkMATH

Gheorghe M, Ipate F, Lefticaru R et al (2013) 3-Col problem modelling using simple kernel P systems. International Journal of Computer Mathematics 90(4):816–830MathSciNetMATHCrossRef

Gutiérrez-Escudero R, Pérez-Jiménez MJ, Rius-Font M (2009) Characterizing tractability by tissue-like P systems. Membrane Computing, Berlin/Heidelberg. Springer, Germany, pp 289–300

Ionescu M, Păun Gh, Yokomori T (2006) Spiking neural P systems. Fundamenta Informaticae 71(2–3):279–308MathSciNetMATH

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C (2016) Shallow non-confluent P systems. In: Proceedings of the 17th International Conference on Membrane Computing (CMC2016), Italy, pp 307–316

Martin-Vide C, Pazos J, Păun Gh, Rodríguez-Patón A (2003) Tissue P systems. Theor Comput Sci 296(2):295–326MathSciNetMATHCrossRef

Macías-Ramos LF, Pérez-Jiménez MJ, Riscos-Núez A et al (2015a) Membrane fission versus cell division: When membrane proliferation is not enough. Theor Comput Sci 608(1):57–65MathSciNetMATHCrossRef

Macías-Ramos LF, Song B, Valencia-Cabrera L, Pan L, Pérez-Jiménez MJ (2015b) Membrane fission: a computational complexity perspective. Complexity 21(6):321–334MathSciNetCrossRef

Papadimitriou CH (1993) Computational Complexity. Addison-Wesley, BostonMATH

Păun A (2002a) Membrane systems with symport/antiport: universality results. Pre-Proceedings of Workshop on Membrane Computing, Curtea de Argeş, Romania, MolCoNet Publication 1:333–343

Păun A, Păun G (2002b) The power of communication: P systems with symport/antiport. New Generation Computing 20(3):295–305MATHCrossRef

Păun A, Păun G, Rozenberg G (2002c) Computing by communication in networks of membranes. Int J Found Comput Sci 13:779–798MathSciNetMATHCrossRef

Pan L, Ishdorj TO (2004) P systems with active membranes and separation rules. Journal of Universal Computer Science 10(5):630–649MathSciNet

Pan L, Pérez-Jiménez MJ (2010) Computational complexity of tissue-like P systems. Journal of Complexity 26:296–315MathSciNetMATHCrossRef

Păun G (2000a) Computing with membranes. J Comput Syst Sci 61(1):108–143. Also in Turku Center for Computer Science–TUCS, Report 208, November 1998

Păun G (2000b) Attacking NP-complete problems. Unconventional Models of Computation, UMC2K, Springer-Verlag pp 94–115

Păun G (2002) Membrane Computing: an Introduction. Springer Science & Business Media, BerlinMATHCrossRef

Păun G, Pérez-Jiménez MJ, Riscos-Núnez A (2008) Tissue P system with cell division. International Journal of Computers, Communications & Control 3(3):295–303CrossRef

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

Peng H, Wang J, Shi P, Riscos-Núñez A, Pérez-Jiménez MJ (2015) An automatic clustering algorithm inspired by membrane computing. Pattern Recogn Lett 68:34–40CrossRef

Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F (2004) The P versus NP problem through cellular computing with membranes. Lect Notes Comput Sci 2950:338–352MATHCrossRef

Pérez-Jiménez MJ (2005) An approach to computational complexity in membrane computing. Lect Notes Comput Sci 3365:85–109MATHCrossRef

Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F (2006) A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics 11(4):423–434MathSciNetMATH

Rozenberg G, Salomaa A (1997) Handbook of Formal Languages, Volume 1. Word, Language, Grammar,

Song B, Pérez-Jiménez MJ, Pan L (2015a) Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division. BioSystems 130:51–58CrossRef

Song B, Pérez-Jiménez MJ, Pan L (2016a) An efficient time-free solution to SAT problem by P systems with proteins on membranes. J Comput Syst Sci 82:1090–1099MathSciNetMATHCrossRef

Song B, Pan L, Pérez-Jiménez MJ (2016b) Cell-like P systems with channel states and symport/antiport rules. IEEE Trans Nanobiosci 15(6):555–566CrossRef

Song T, Pan L (2015b) Spiking neural P systems with rules on synapses working in maximum spiking strategy. IEEE Trans Nanobiosci 14(4):465–477CrossRef

Song T, Pan L (2016) Spiking neural P systems with request rules. Neurocomputing 193:193–200CrossRef

Song B, Song T, Pan L (2017a) A time-free uniform solution to subset sum problem by tissue P systems with cell division. Mathematical Structures in Computer Science 27(1):17–32MathSciNetMATHCrossRef

Song B, Zhang C, Pan L (2017b) Tissue-like P systems with evolutional symport/antiport rules. Inf Sci 378:177–193MathSciNetCrossRef

Sosík P, Ludĕk C (2014) Computational power of cell separation in tissue P systems. Inf Sci 279:805–815MathSciNetMATHCrossRef

Sosík P, Ludĕk C (2015) A limitation of cell division in tissue P systems by PSPACE. J Comput Syst Sci 81(2):473–484MathSciNetMATHCrossRef

Valencia-Cabrera L, Song B, Macías-Ramos LF, Pan L, Pérez-Jiménez MJ (2015) Computational Efficiency of P Systems with Symport/Antiport Rules and Membrane Separation. Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, Sevilla, pp 325-370

Zandron C, Leporati A, Ferretti C et al (2008) On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. Fundamenta Informaticae 87(1):79–91MathSciNetMATH

Zhang G, Gheorghe M, Pan L, Pérez-Jiménez MJ (2014a) Evolutionary membrane computing: a comprehensive survey and new results. Inf Sci 279:528–551CrossRef

Zhang X, Pan L, Păun A (2015) On the universality of axon P systems. IEEE Transactions on Neural Networks and Learning Systems 26(11):2816–2829MathSciNetCrossRef

Zhang G, Rong H, Neri F, Pérez-Jiménez MJ (2014b) An optimization spiking neural P system for approximately solving combinatorial optimization problems. Int J Neural Syst 24(5):1–16CrossRef

Title: A uniform solution to SAT problem by symport/antiport P systems with channel states and membrane division
Authors: Suxia Jiang
Yanfeng Wang
Yansen Su
Publication date: 19-06-2018
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 12/2019
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-018-3254-2

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 "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 12/2019

Automatic identification of characteristic points related to pathologies in electrocardiograms to design expert systems

Accelerating differential evolution based on a subset-to-subset survivor selection operator

An elitism-based self-adaptive multi-population Jaya algorithm and its applications

A biased random key genetic algorithm for the protein–ligand docking problem

MS-ACO: a multi-stage ant colony optimization to refute complex software systems specified through graph transformation

An angle-based method for measuring the semantic similarity between visual and textual features

Premium Partner