nach oben

Natural Computing

Erschienen in:

01.03.2015

On the complexity of occurrence and convergence problems in reaction systems

verfasst von: Enrico Formenti, Luca Manzoni, Antonio E. Porreca

Erschienen in: Natural Computing | Ausgabe 1/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Reaction systems are a model of computation inspired by biochemical reactions introduced by Ehrenfeucht and Rozenberg. Two problems related to the dynamics (the evolution of the state with respect to time) of reaction systems, namely, the occurrence and the convergence problems, were recently investigated by Salomaa. In this paper, we prove that both problems are PSPACE-complete when the numerical parameter of the problems (i.e. the time step when a specified element must appear) is given as input. Moreover, they remain PSPACE-complete even for minimal reaction systems.

Vorheriger Artikel A novel hybrid artificial bee colony algorithm with crossover operator for numerical optimization

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

Ehrenfeucht A, Rozenberg G (2007) Reaction systems. Fundamenta Informaticae 75:263–280. http://iospress.metapress.com/content/b86t11hryvwq69l0/

Ehrenfeucht A, Rozenberg G (2009) Introducing time in reaction systems. Theor Comput Sci 410(4):310–322. doi:10.1016/j.tcs.2008.09.043

Manzoni L, Porreca AE (2013) Reaction systems made simple: a normal form and a classification theorem. In: Mauri G, Dennunzio A, Manzoni L, Porreca AE (eds) Unconventional computation and natural computation, 12th international conference, UCNC 2013, Lecture Notes in Computer Science, vol 7956, Springer, New York, pp 150–161. doi:10.1007/978-3-642-39074-6_15

Manzoni L, Poças D, Porreca AE (2014) Simple reaction systems and their classification. Int J Found Comput Sci 18(6):1197

Papadimitriou CH (1993) Computational complexity. Addison-Wesley, Reading

Salomaa A (2013a) Functional constructions between reaction systems and propositional logic. Int J Found Comput Sci 24(1):147–159. doi:10.1142/S0129054113500044

Salomaa A (2013b) Minimal and almost minimal reaction systems. Nat Comput 12(3):369–376. doi:10.1007/s11047-013-9372-y.

Sutner K (1995) On the computational complexity of finite cellular automata. J Comput Syst Sci 50(1):87–97. doi:10.1006/jcss.1995.1009

Titel: On the complexity of occurrence and convergence problems in reaction systems
verfasst von: Enrico Formenti
Luca Manzoni
Antonio E. Porreca
Publikationsdatum: 01.03.2015
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2015
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-014-9456-3

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 1/2015

CoSMoS special issue editorial

Filling gaps in simulation of complex systems: the background and motivation for CoSMoS

Using a simulated Wolbachia infection mechanism to improve multi-objective evolutionary algorithms

Simulation methods for quantum walks on graphs applied to formal language recognition

Non-standard discretization of biological models

Understanding tissue morphology: model repurposing using the CoSMoS process

Premium Partner