Linear time analysis of properties of conflict-free and general Petri nets

DOI10.1016/J.TCS.2010.09.030MaRDI QIDQ620942zbMATH OpenOpenAlexFDO

Authors Paola Alimonti, E. Feuerstein, Luigi Laura, Umberto Nanni

Publication date 2 February 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.09.030

zbMATH Keywords

boundednessdirected hypergraphsPetri netslivenessmarked graphsincremental algorithmsconflict-free Petri netscoverability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• scientific article; zbMATH DE number 512938
• scientific article; zbMATH DE number 176140
• A solution to the covering problem for 1-bounded conflict-free Petri nets using linear programming
• Deciding a class of path formulas for conflict-free Petri nets
• Priority conflict-free Petri nets

Cites work

• scientific article; zbMATH DE number 3885321 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3471613 (Why is no real title available?)
• scientific article; zbMATH DE number 3557247 (Why is no real title available?)
• scientific article; zbMATH DE number 559221 (Why is no real title available?)
• A Note on Persistent Petri Nets
• A decidability theorem for a class of vector-addition systems
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A polynomial-time algorithm to decide liveness of bounded free choice nets
• A taxonomy of fairness and temporal logic problems for Petri nets
• A unified approach for deciding the existence of certain petri net paths
• An Algorithm for the General Petri Net Reachability Problem
• An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
• Complexity of some problems in Petri nets
• Complexity results for 1-safe nets
• Directed hypergraphs and applications
• Directed recursive labelnode hypergraphs: A new representation-language
• Dynamic maintenance of directed hypergraphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Graph Algorithms for Functional Dependency Manipulation
• Introduction to algorithms
• Linear connectivity problems in directed hypergraphs
• Marked directed graphs
• On the computational power of pushdown automata
• On-line algorithms for polynomially solvable satisfiability problems
• Parallel program schemata
• Partially dynamic maintenance of minimum weight hyperpaths
• Problems concerning fairness and temporal logic for conflict-free Petri nets
• Properties of Conflict-Free and Persistent Petri Nets
• The covering and boundedness problems for vector addition systems

Cited in

(9)

• Reachability analysis of low-order discrete state reaction networks obeying conservation laws
• A valuation-based analysis of conflict-free Petri nets
• The formalization of decision-free Petri net
• scientific article; zbMATH DE number 3850481 (Why is no real title available?)
• Static analysis of biological regulatory networks dynamics using abstract interpretation
• Trace nets and conflict-free computations
• A solution to the covering problem for 1-bounded conflict-free Petri nets using linear programming
• Directed hypergraphs: introduction and fundamental algorithms -- a survey
• Lower and upper bounds of shortest paths in reachability graphs

This page was built for publication: Linear time analysis of properties of conflict-free and general Petri nets

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