Decidability and complexity of Petri nets with unordered data

DOI10.1016/j.tcs.2011.05.007zbMath1231.68172WikidataQ57831211 ScholiaQ57831211MaRDI QIDQ554219

Fernando Rosa-Velardo, David de Frutos-Escrig

Publication date: 29 July 2011

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

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

zbMATH Keywords

boundedness; reachability; Petri nets; well-structured transition systems; pure names

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q60: Specification and verification (program logics, model checking, etc.)

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Unnamed Item, Soundness Verification of Data-Aware Process Models with Variable-to-Variable Conditions, SMT-based verification of data-aware processes: a model-theoretic approach, Dynamic Networks of Timed Petri Nets, WQO dichotomy for 3-graphs, The ideal view on Rackoff's coverability technique, A Non-Deterministic Multiset Query Language, From DB-nets to Coloured Petri Nets with Priorities, Correctness Notions for Petri Nets with Identifiers, Model checking Petri nets with names using data-centric dynamic systems, Ordinal recursive complexity of unordered data nets, Multiset rewriting for the verification of depth-bounded processes with name binding, Data and process resonance. Identifier soundness for models of information systems, Petri nets with name creation for transient secure association, Coverability Trees for Petri Nets with Unordered Data, Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture

Cites Work

• A classification of the expressive power of well-structured transition systems
• A calculus of mobile processes. I
• Mobile ambients
• Algorithmic analysis of programs with well quasi-ordered domains.
• On the Expressiveness of Mobile Synchronizing Petri Nets
• Cost Soundness for Priced Resource-Constrained Workflow Nets
• Decidability Problems in Petri Nets with Names and Replication
• Constraint-based automatic verification of abstract models of multithreaded programs
• Instance Deadlock: A Mystery behind Frozen Programs
• Forward Analysis for Petri Nets with Name Creation
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• Forward Analysis for WSTS, Part II: Complete WSTS
• Petri Nets as Token Objects
• Applications and Theory of Petri Nets 2004
• Applications and Theory of Petri Nets 2005
• Well-structured transition systems everywhere!
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item