错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the spectrum between reaction systems and string rewriting

  • Artiom Alhazov,
  • Rudolf Freund,
  • Sergiu Ivanov

摘要

Reaction systems are a model of computing aiming to formalize biochemistry by capturing the qualitative relations between the species, and explicitly discarding any accounts of multiplicity. From the point of view of the formal language theory, this situates them in the realm of set rewriting. In this work, we propose a series of extensions of reaction systems to use strings. These extensions form a spectrum in the sense that all of them honor the hallmark features of the original model: the threshold principle and the non-permanency principle. We thoroughly discuss the details of the structure and the behavior of these variants, and commence studying their expressive power by comparing them to some classic models of computing.