• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Minimal and Almost Minimal Reaction Systems

Arto Salomaa, Minimal and Almost Minimal Reaction Systems. Natural Computing 12(3), 369–376, 2013.

Abstract:

We compare minimal reaction systems, where the
number of resources equals 2, with almost minimal reaction system, where the number of resources is at most 3. The difference turns out to be huge. While many central problems for minimal systems are of low polynomial cpmplexity, the same problems in almost minimal case are NP- or co-NP-complete. Similar conclusions hold true for maximal sequence lengths in the two cases.

BibTeX entry:

@ARTICLE{jSalomaa_Arto13b,
  title = {Minimal and Almost Minimal Reaction Systems},
  author = {Salomaa, Arto},
  journal = {Natural Computing},
  volume = {12},
  number = {3},
  publisher = {Springer-Verlag},
  pages = {369–376},
  year = {2013},
  keywords = {reaction system, reactant, inhibitor, sequence length, NP-completeness },
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication