Elsevier

Theoretical Computer Science

Volume 467, 7 January 2013, Pages 12-29
Theoretical Computer Science

On the coverability and reachability languages of monotonic extensions of Petri nets

https://doi.org/10.1016/j.tcs.2012.09.021Get rights and content
Under an Elsevier user license
open archive

Abstract

We apply language theory to compare the expressive power of infinite-state models that extend Petri nets with features like coloured tokens and/or whole place operations. Specifically, we consider extensions of Petri nets in which tokens carry pure names dynamically generated with special ν-transitions (ν-PN) and compare their expressiveness with transfer and reset nets with black indistinguishable tokens (Affine Well-Structured Nets), and nets in which tokens carry data taken from a linearly ordered domain (Data nets and CMRS). All these models are well-structured transition systems. In order to compare these models we consider the families of languages they recognize, using coverability as the accepting condition. With this criterion, we prove that ν-PNs are in between AWNs and Data Nets/CMRS, but equivalent to an extension of ν-PN with whole-place operations. These results extend the currently known classification of the expressive power of well-structured transition systems. Finally, we study several problems regarding (coverability) languages of AWN and ν-PN.

Keywords

Language theory
Petri nets
Expressive power
Well structured transition systems

Cited by (0)