nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

A Uniform Family of Tissue P Systems with Protein on Cells Solving 3-Coloring in Linear Time

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

Erschienen in: Unconventional Computation and Natural Computation

Verlag: Springer International Publishing

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. In this new variant, these objects called proteins are used to obtain a new solution where the number of rules is lesser than that appears in the original solution with tissue P systems. The number of steps to obtain the solution is lesser than the conventional tissue P system. This is a strong point when someone wants to implement a solution in a practical way.

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

Vorheriges Kapitel Simulation of the 2JLP Gene Assembly Process in Ciliates

Nächstes Kapitel Asynchronous Dynamics of Boolean Automata Double-Cycles

Alhazov, A., Freund, R., Oswald, M.: Tissue P systems with antiport rules and small numbers of symbols and cells. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 100–111. Springer, Heidelberg (2005) CrossRef

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

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

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

Díaz-Pernil, D., Gutierrez-Naranjo, M.A., Perez-Jimenez, M.J., Riscos-Nunez, A.: A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoret. Comput. Sci. 404(1–2), 76–87 (2008)CrossRefMathSciNetMATH

Freund, R., Paun, G., Pérez-jiménez, M.J.: Tissue P systems with channel states. Theoret. Comput. Sci. 330, 101–116 (2005)CrossRefMathSciNetMATH

Garey, M.R., Johnson, D.S.: Computers and Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979) MATH

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

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

10.

Krishna, S.N., Lakshmanan, K., Rama, R.: Tissue P systems with contextual and rewriting rules. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC-CdeA 2002, LNCS, vol. 2597, pp. 339–351. Springer, Heidelberg (2003) CrossRef

11.

Song, B., Pan, L., Pérez-Jiménez, M.J.: Tissue P systems with protein on cells. Fundamenta Informaticae XXI, 1001–1030 (2001)

12.

Song, B., Song, T., Pan, L.: Time-free solution to SAT problem by P systems with active membranes and standard cell division rules. Natural Computing (2014). doi: 10.1007/s11047-014-9471-4

13.

Song, B., Pan, L.: Computational efficiency and universality of timed P systems with active membranes. Theoret. Comput. Sci. 567, 74–86 (2015)CrossRefMathSciNet

14.

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

15.

Martín-Vide, C., Pazos, J., Păun, G., Rodríguez-Patón, A.: A new class of symbolic abstract neural nets: tissue P systems. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, p. 290. Springer, Heidelberg (2002) CrossRef

16.

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

17.

Păun, G.: Membrane Computing: An Introduction. Springer-Verlag, Berlin (2002) CrossRef

18.

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

19.

Păun, G., Rozenberg, G., Salomaa, A. (eds.): Handbook of Membrane Computing. Oxford University Press, Cambridge (2009)

20.

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

21.

Stockmeyer, L.J.: Planar 3-colorability is NP-complete. SIGACT News 5(3), 19–25 (1973)CrossRefMathSciNet

Titel: A Uniform Family of Tissue P Systems with Protein on Cells Solving 3-Coloring in Linear Time
verfasst von: T. Mathu
Hepzibah A. Christinal
Daniel Díaz-Pernil
Verlag: Springer International Publishing
Buch: Unconventional Computation and Natural Computation
Print ISBN: 978-3-319-21818-2

Electronic ISBN: 978-3-319-21819-9

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-21819-9_18

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"

Premium Partner