Skip to Main content Skip to Navigation
New interface
Journal articles

On the Complexity of Concurrent Multiset Rewriting

Marin Bertier 1 Matthieu Perrin 2, 3 Cédric Tedeschi 4 
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
3 GDD - Gestion de Données Distribuées [Nantes]
LINA - Laboratoire d'Informatique de Nantes Atlantique
4 MYRIADS - Design and Implementation of Autonomous Distributed Systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : In this paper, we are interested in the runtime complexity of programs based on multiset rewriting. The motivation behind this work is the study of the complexity of chemistry-inspired programming models, which recently regained momentum due to their adequacy to the programming of large autonomous systems. In these models, data are most of the time left unstructured in a container, or more formally, a multiset. The program to be applied to this multiset is specified as a set of conditioned rules rewriting the multiset. At run time, these rewrite operations are applied concurrently, until no rule can be applied anymore (the set of elements they need cannot be found in the multiset anymore). A limitation of these models stands in their complexity: each computation step may require a complexity in O(n^k) where n denotes the number of elements in the multiset, and k is the size of the subset of elements needed to trigger a given rule. By analogy with chemistry, such elements can be called reactants. In this paper, we explore the possibility of improving the complexity of searching reactants through a static analysis of the rules' condition. In particular, we give a char-acterisation of this complexity, by analogy to the subgraph isomorphism problem. Given a rule R, we define its rank rk(R) and its calibre C(R), allowing us to exhibit an algorithm with a complexity in O(n^(rk(R)+C(R))) for searching reactants, while showing that rk(R) + C(R) ≤ k and that rk(R) + C(R) < k most of the time.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Cédric Tedeschi Connect in order to contact the contributor
Submitted on : Monday, June 6, 2016 - 9:34:45 AM
Last modification on : Friday, July 8, 2022 - 10:06:19 AM


Files produced by the author(s)



Marin Bertier, Matthieu Perrin, Cédric Tedeschi. On the Complexity of Concurrent Multiset Rewriting. International Journal of Foundations of Computer Science, 2016, 27 (1), ⟨10.1142/S0129054116500052⟩. ⟨hal-01326849⟩



Record views


Files downloads