Multiset Reaction Systems

: Bottoni, Paolo; Mitrana, Victor; Petre, Ion

: Jiménez López, M. Dolores; Vaszil, György

: 1

Publisher: Springer Nature Switzerland

: 2025

: Lecture Notes in Computer Science

: Languages of Cooperation and Communication: Essays Dedicated to Erzsébet Csuhaj-Varjú to Celebrate Her Scientific Career

: Lecture Notes in Computer Science

: 15840

: 179

: 193

: 978-3-031-97273-7

: 978-3-031-97274-4

: 0302-9743

: 1611-3349

DOI: https://doi.org/10.1007/978-3-031-97274-4_11

: https://doi.org/10.1007/978-3-031-97274-4_11

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.

:
This study was supported by the Ministry of Research, Innovation, and Digitalization through the Core Program of the National Research, Development, and Innovation Plan 2022-2027, project no. PN 23-02-0101-Contract No. 7N/2023. It was also supported by the Ministry of Research, Innovation, and Digitalization through the Romanian National Recovery and Resilience Plan (PNRR), Pillar III, Component C9/Investment no. 8 (I8) - contract CF 68 and contract CF 53.