Petri Nets are a formalism for describing coordinated interactions between independent entities, called transitions, by means of synchronized token exchange through places. Tuplespaces are an abstraction of the shared memory concept providing means for loosely-coupled coordination between individual components. In the tuplespace model, coordination between applications is achieved by production and blocking consumption of tuples which are communicated over tuplespace buffers. On the basis of the conceptual similarities of Petri nets and tuplespaces, we investigate in this paper whether on the one hand Petri nets are a suitable notation for modeling tuplespace-based applications; on the other hand, we argue that tuplespaces are a suitable platform for execution of applications modeled as Petri net-based workflows by describing and evaluating two approaches to execute Petri nets using tuplespace-based middleware.