nach oben

Natural Computing

Erschienen in:

01.12.2010

On the computational complexity of spiking neural P systems

verfasst von: Turlough Neary

Erschienen in: Natural Computing | Ausgabe 4/2010

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

It is shown here that there is no standard spiking neural P system that simulates Turing machines with less than exponential time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent of the input length. Following this, we construct a universal spiking neural P system with exhaustive use of rules that simulates Turing machines in linear time and has only 10 neurons.

Vorheriger Artikel Quantum security in wireless sensor networks

Nächster Artikel Output concepts for accelerated Turing machines

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

In a similar table given in Neary (2010a) the time/space complexity given for a number of the systems is incorrect due to an error copied from Korec’s paper (Korec 1996). For more see the last paragraph of Sect. 3.

Chen H, Ionescu M, Ishdorj T (2006) On the efficiency of spiking neural P systems. In: Gutiérrez-Naranjo MA, Păun G, Riscos-Núñez A, Romero-Campero FJ (eds) Proceedings of fourth brainstorming week on membrane computing, Sevilla, Spain, Feb 2006, pp 195–206

Fischer PC, Meyer A, Rosenberg A (1968) Counter machines and counter languages. Math Syst Theory 2(3):265–283MATHCrossRefMathSciNet

Ionescu M, Sburlan D (2007) Some applications of spiking neural P systems. In: Eleftherakis G, Kefalas P, Păun G (eds) Proceedings of the eighth workshop on membrane computing, Thessaloniki, Greece, June 2007, pp 383–394

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

Ionescu M, Păun G, Yokomori T (2007) Spiking neural P systems with exhaustive use of rules. Int J Unconv Comput 3(2):135–153

Korec I (1996) Small universal register machines. Theor Comput Sci 168(2):267–301MATHCrossRefMathSciNet

Leporati A, Zandron C, Ferretti C, Mauri G (2007) Solving numerical NP-complete problems with spiking neural P systems. In: Eleftherakis G, Kefalas P, Păun G, Rozenberg G, Salomaa A (eds) 8th international workshop, WMC 2007, volume 4860 of LNCS, Thessaloniki, Greece, June 2007, pp 336–352

Leporati A, Zandron C, Ferretti C, Mauri G (2009) On the computational power of spiking neural P systems. Int J Unconvent Comput 5(5):459–473

Neary T (2008a) Presentation at the international workshop on computing with biomolecules (CBM 2008). Available at http://www.emcc.at/UC2008/Presentations/CBM5.pdf

Neary T (2008b) On the computational complexity of spiking neural P systems. In: Calude CS, Félix J, Freund Costa R, Oswald M, Rozenberg G (eds) Unconventional computation, 7th international conference, UC 2008, volume 5204 of LNCS, Vienna, Austria, Aug 2008. Springer, pp 189–205

Neary T (2008c) A small universal spiking neural P system. In: Csuhaj-Varjú E, Freund R, Oswald M, Salomaa K (eds) International workshop on computing with biomolecules, Vienna, Austria, Aug 2008. Austrian Computer Society, pp 65–74

Neary T (2009) A boundary between universality and non-universality in spiking neural P systems. arXiv:0912.0741v3 [cs.CC]

Neary T (2010a) A boundary between universality and non-universality in spiking neural P systems. In: Dediu AH, Fernau H, Martín-Vide C (eds) 4th international conference on language and automata theory and applications, LATA 2010, volume 6031 of LNCS, Trier, Germany, May 2010. Springer, pp 475–487

Neary T (2010b) A universal spiking neural P system with 11 neurons. In: Eleventh international conference on membrane computing (CMC11), Jena, Germany, Aug 2010

Păun G (2002) Membrane computing: an introduction. Springer, BerlinMATH

Păun A, Păun G (2005) Small universal spiking neural P systems. Biosystems 90(1):48–60CrossRef

Schroeppel R (1972) A two counter machine cannot calculate 2ⁿ. Technical report AIM-257, A.I. memo 257. Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge

Zhang X, Jiang Y, Pan L (2008a) Small universal spiking neural P systems with exhaustive use of rules. In: Kearney D, Nguyen V, Gioiosa G, Hendtlass T (eds) 3rd international conference on bio-inspired computing: theories and applications (BICTA 2008), Adelaide, Australia, Oct 2008. IEEE, pp 117–128

Zhang X, Zeng X, Pan L (2008b) Smaller universal spiking neural P systems. Fundamenta Informaticae 87(1):117–136MATHMathSciNet

Titel: On the computational complexity of spiking neural P systems
verfasst von: Turlough Neary
Publikationsdatum: 01.12.2010
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 4/2010
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-010-9213-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 4/2010

A synthetic genetic circuit whose signal-response curve is temperature-tunable from band-detection to sigmoidal behaviour

Introduction to special issue on Optical SuperComputing

Output concepts for accelerated Turing machines

On the verification of membrane systems with dynamic structure

A relation by palindromic subwords

Preface to the Special Issue Unconventional Computing 2008

Premium Partner