High undecidability of weak bisimilarity for Petri nets

DOI10.1007/3-540-59293-8_206zbMath1496.68229OpenAlexW2113148168MaRDI QIDQ5096742

Petr Jančar

Publication date: 18 August 2022

Published in: TAPSOFT '95: Theory and Practice of Software Development (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59293-8_206

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Hierarchies of computability and definability (03D55)

Related Items

Undecidability of bisimilarity for Petri nets and some related problems, Weak bisimilarity and regularity of context-free processes is EXPTIME-hard, On the computational complexity of bisimulation, redux, EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system, Reachability is decidable for weakly extended process rewrite systems

Cites Work

• Handbook of mathematical logic. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis, A. S. Troelstra. 2nd printing
• On the reachability problem for 5-dimensional vector addition systems
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Bisimulation equivalence is decidable for all context-free processes
• An Algorithm for the General Petri Net Reachability Problem
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item