×

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)
Full Text: DOI