Catalytic Petri Nets are Turing Complete

Ciobanu Gabriel;PINNA, GIOVANNI MICHELE

2012-01-01

---

Abstract

In this paper we introduce a class of Petri nets, called catalytic Petri nets, and a suitable firing strategy where transitions are fired only when they use tokens from specific places, called catalytic places. By establishing a one-to-one relationship with catalytic membrane systems, we can prove that the class of catalytic Petri nets with at least two catalytic places is Turing complete.