Complexity results for problems of communication-free Petri nets and related formalisms

DOI10.3233/FI-2015-1170MaRDI QIDQ2805419zbMATH OpenOpenAlexFDO

Authors Ernst W. Mayr, Jeremias Weihmann

Publication date 11 May 2016

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2015-1170

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• scientific article; zbMATH DE number 4037227
• Completeness results for generalized communication-free Petri nets with arbitrary edge multiplicities
• The complexity of problems involving structurally bounded and conservative Petri nets
• Completeness results for generalized communication-free Petri nets with arbitrary arc multiplicities
• SOME COMPLEXITY RESULTS FOR RINGS OF PETRI NETS
• Nonprimitive recursive complexity and undecidability for Petri net equivalences
• scientific article; zbMATH DE number 1302047
• \(\omega\)-Petri nets: algorithms and complexity
• Complexity analysis of continuous Petri nets
• Complexity analysis of continuous Petri nets

Cited in

(9)

• Flatness and Complexity of Immediate Observation Petri Nets
• Results on equivalence, boundedness, liveness, and covering problems of BPP-Petri nets
• Completeness results for generalized communication-free Petri nets with arbitrary arc multiplicities
• Completeness results for generalized communication-free Petri nets with arbitrary edge multiplicities
• Context-free commutative grammars with integer counters and resets
• scientific article; zbMATH DE number 1560298 (Why is no real title available?)
• The complexity of problems involving structurally bounded and conservative Petri nets
• Approximating Petri net reachability along context-free traces
• A solution to the covering problem for 1-bounded conflict-free Petri nets using linear programming

This page was built for publication: Complexity results for problems of communication-free Petri nets and related formalisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805419)