Benutzer: Gast  Login
Titel:

Completeness Results for Generalized Communication-free Petri Nets with Arbitrary Edge Multiplicities

Autor(en):
Ernst W. Mayr; Jeremias Weihmann
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...     »
Stichworte:
Petri nets; Basic Parallel Processes; communication-free Petri nets; commutative context-free grammars; generalized communication-free Petri nets; generalizations; general edge multiplicities
Jahr:
2013
Sprache:
en
 BibTeX