A multiset reaction system is an extension of the classical reaction system model with three key differences. First, all components of a reaction are now multisets and not sets. Second, it modifies the permanency principle: in this model, resources which are not consumed by application of reactions do not vanish from the system, even if they are not supported by any enabled reaction. Third, each resource is available in a finite, specific quantity, which may constrain the number of reactions that can access it concurrently. As a result, the model is inherently quantitative and nondeterministic, and it operates on multisets of resources rather than on simple sets. We investigate several modes of simultaneous and parallel enabling of reaction within this framework and demonstrate that all of them can be effectively simulated using sequential enabling. Additionally, we prove that the computational power of multiset reaction systems with sequential evolution is equivalent to that of multiset Turing machines.

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

Multiset Reaction Systems

  • Paolo Bottoni,
  • Victor Mitrana,
  • Ion Petre

摘要

A multiset reaction system is an extension of the classical reaction system model with three key differences. First, all components of a reaction are now multisets and not sets. Second, it modifies the permanency principle: in this model, resources which are not consumed by application of reactions do not vanish from the system, even if they are not supported by any enabled reaction. Third, each resource is available in a finite, specific quantity, which may constrain the number of reactions that can access it concurrently. As a result, the model is inherently quantitative and nondeterministic, and it operates on multisets of resources rather than on simple sets. We investigate several modes of simultaneous and parallel enabling of reaction within this framework and demonstrate that all of them can be effectively simulated using sequential enabling. Additionally, we prove that the computational power of multiset reaction systems with sequential evolution is equivalent to that of multiset Turing machines.