nach oben

Natural Computing

Erschienen in:

19.11.2016

A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time

verfasst von: A. Hepzibah Christinal, Daniel Díaz-Pernil, T. Mathu

Erschienen in: Natural Computing | Ausgabe 2/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A new variant of tissue P systems called tissue P system with protein on cells is used in this paper. It has the ability to move proteins between cells. It is inspired from the biology that the cells communicate by sending and receiving signals. Signals most often move through the cell by passing from protein to protein. In tissue P systems with protein on cells, multisets of objects together with proteins between cells are exchanged. We present in this paper a linear solution of the 3-coloring problem, a well known NP-complete problem.

Vorheriger Artikel Extended spiking neural P systems with white hole rules and their red–green variants

Nächster Artikel Some new results of P colonies with bounded parameters

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

We can observe some of the rules \(r_{13}\) could be applied before, with rules \(r_{11}\) and \(r_{12}\), but not all of them.

Alhazov A, Freund R, Oswald M (2005) Tissue P systems with antiport rules and small numbers of symbols and cells. Lect Notes Comput Sci 3572:100–111MathSciNetCrossRefMATH

Appel K, Haken W (1977) Every planar map is 4-colorable—1: discharging. Ill J Math 21:429–490MathSciNetMATH

Appel K, Haken W (1977) Every planar map is 4-colorable—2: reducibility. Ill J Math 21:491–567MathSciNetMATH

Bernardini F, Gheorghe M (2005) Cell communication in tissue P systems and cell division in population P systems. Soft Comput 9(9):640–649CrossRefMATH

Díaz-Pernil D, Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A (2008) A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theor Comput Sci 404(1–2):76–87MathSciNetCrossRefMATH

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

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New YorkMATH

Gheorghe M, Ipate F, Lefticaru R, Pérez-Jiménez MJ, Turcanu A, Valencia-Cabrera L, Garcia-Quismondo M, Mierla L (2013) 3-Col problem modelling using simple kernel P systems. Int J Comput Math 90(4):816–830MathSciNetCrossRefMATH

Krishna SN, Lakshmanan K, Rama R (2003) Tissue P systems with contextual and rewriting rules. Lect Notes Comput Sci 2597:339–351MathSciNetCrossRefMATH

Martín-Vide C, Pazos J, Păun G, Rodríguez Patón (2002) A new class of symbolic abstract neural nets: tissue P systems. Lect Notes Comput Sci 2387:290–299MathSciNetCrossRefMATH

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

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

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

Păun G (2002) Membrane computing. An introduction. Springer, BerlinCrossRefMATH

Păun G, Pérez-Jiménez MJ, Riscos-Nunez A (2008) Tissue P system with cell division. Int J Comput Commun Control 3(3):295–303CrossRef

Păun G, Rozenberg G, Salomaa A (eds) (2009) Handbook of membrane computing. Oxford University Press, Cambridge

Song B, Pan L, Pérez-Jiménez MJ (2001) Tissue P systems with protein on cells. Fundam Inf XXI:1001–1030MATH

Stockmeyer LJ (1973) Planar 3-colorability is NP-complete. SIGACT News 5(3):19–25MathSciNetCrossRef

Titel: A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time
verfasst von: A. Hepzibah Christinal
Daniel Díaz-Pernil
T. Mathu
Publikationsdatum: 19.11.2016
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2018
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-016-9590-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2018

Extended spiking neural P systems with white hole rules and their red–green variants

Preface

Model-based computation

Erratum to: Computing maximal and minimal trap spaces of Boolean networks

Language recognition power and succinctness of affine automata

An all-optical soliton FFT computational arrangement in the 3NLSE-domain