A language-based comparison of extensions of petri nets with and without whole-place operations

Abstract. We use language theory to study the relative expressiveness of infinite-state models laying in between finite automata and Turing machines. We focus here our attention on well structured transition systems that extend Petri nets. For these models, we study the impact of whole-place operations like transfers and resets on nets with indistinguishable tokens and with tokens that carry data over an infinite domain. Our measure of expressiveness is defined in terms of the class of languages recognized by a given model using coverability of a configuration as accepting condition. Our main result is that, perhaps surprisingly, whole-place operations augment the expressive power of Petri nets only in the case of black indistinguishable tokens. The results of our analysis can be used to build a com-plete hierarchy of well-structured models like Petri nets, affine well-structured nets, lossy fifo channel systems, constrained multiset rewriting systems, and data nets