Process Rewrite Systems

Many formal models for infinite-state concurrent systems are equivalent to special classes of rewrite systems. We classify these models by their expressiveness and define a hierarchy of classes of rewrite systems. We show that this hierarchy is strict with respect to bisimulation equivalence. The most general and most expressive class of systems in this hierarchy is called process rewrite systems (PRS). They subsume Petri nets, PA-processes, and pushdown processes and are strictly more expressive than any of these. Intuitively, PRS can be seen as an extension of Petri nets by subroutines that can return a value to their caller. We show that the reachability problem is decidable for PRS. It is even decidable if there is a reachable state that satisfies certain properties that can be encoded in a simple logic. Thus, PRS are more expressive than Petri nets, but not Turing-powerful.

Authors

• Richard Mayr

Keywords

No keywords are indexed for this paper.