A3 Refereed book chapter or chapter in a compilation book
Multiset Reaction Systems
Authors: Bottoni, Paolo; Mitrana, Victor; Petre, Ion
Editors: Jiménez López, M. Dolores; Vaszil, György
Edition: 1
Publisher: Springer Nature Switzerland
Publication year: 2025
Journal: Lecture Notes in Computer Science
Book title : Languages of Cooperation and Communication: Essays Dedicated to Erzsébet Csuhaj-Varjú to Celebrate Her Scientific Career
Journal name in source: Lecture Notes in Computer Science
Series title: Lecture Notes in Computer Science
Number in series: 15840
First page : 179
Last page: 193
ISBN: 978-3-031-97273-7
eISBN: 978-3-031-97274-4
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-97274-4_11
Web address : 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.
Funding information in the publication:
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.
