User: Guest  Login
Author(s):
Ernst W. Mayr; Jeremias Weihmann 
Title:
Completeness Results for Generalized Communication-free Petri Nets with Arbitrary Edge Multiplicities 
Abstract:
We investigate gcf-Petri nets, a generalization of communication-free Petri nets allowing arbitrary edge multiplicities, and characterized by the sole restriction that each transition has at most one incoming edge. We use canonical firing sequences with nice properties for gcf-PNs to show that the RecLFS, (zero-)reachability, covering, and boundedness problems of gcf-PNs are in PSPACE. By showing, how PSPACE-Turing machines can be simulated by gss-PNs, a subclass of gcf-PNs where additionally al...    »
 
Keywords:
Petri nets; Basic Parallel Processes; communication-free Petri nets; commutative context-free grammars; generalized communication-free Petri nets; generalizations; general edge multiplicities 
Year:
2013 
Language:
en