Petri net implementations by a universal cell space. (English) Zbl 0559.68056
The authors show: the safe behaviour of Petri nets (condition/event systems) can be simulated by asynchronous cell spaces of dimension 2 with 6-state 9-neighbour cells. A minor modification gives a simulation by nondeterministic synchronous cell spaces. Starting with the class of standard Petri nets - which are compositions of components of three simple types (fan in, fan out, decision) and known to simulate arbitrary safe Petri nets - they construct a cell space which, given a simple coding of a standard Petri net as initial configuration, simulates the Petri net. So the paper shows the universality of cell spaces in respect to concurrent computations. The paper is clear, precise and well readable.
Reviewer: H.Müller
MSC:
68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
68Q80 | Cellular automata (computational aspects) |
68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |