Undecidability of bisimilarity for Petri nets and some related problems
From MaRDI portal
Publication:672326
DOI10.1016/0304-3975(95)00037-WzbMath0873.68147WikidataQ127613938 ScholiaQ127613938MaRDI QIDQ672326
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Resource Bisimilarity in Petri Nets is Decidable ⋮ Trace Inclusion for One-Counter Nets Revisited ⋮ Causality, Behavioural Equivalences, and the Security of Cyberphysical Systems ⋮ Trace inclusion for one-counter nets revisited ⋮ Encoding Asynchronous Interactions Using Open Petri Nets ⋮ Bisimulation equivalence is decidable for one-counter processes ⋮ Interleaving vs True Concurrency: Some Instructive Security Examples ⋮ Undecidability of accordance for open systems with unbounded message queues ⋮ Verifying chemical reaction network implementations: a bisimulation approach ⋮ Decidability of Two Truly Concurrent Equivalences for Finite Bounded Petri Nets ⋮ Reversing Unbounded Petri Nets ⋮ On the expressiveness and decidability of higher-order process calculi ⋮ Comparing the Expressiveness of Timed Automata and Timed Extensions of Petri Nets ⋮ Petri nets and regular processes ⋮ Parametrized automata simulation and application to service composition ⋮ Team bisimilarity, and its associated modal logic, for BPP nets ⋮ Deciding bisimulation and trace equivalences for systems with many identical processes ⋮ Recursive Petri nets ⋮ Undecidability of performance equivalence of Petri nets ⋮ Computable fixpoints in well-structured symbolic model checking ⋮ On the decidability of fragments of the asynchronous π-calculus ⋮ On the computational complexity of bisimulation, redux ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ Nonprimitive recursive complexity and undecidability for Petri net equivalences ⋮ Decidability of model checking with the temporal logic EF ⋮ Deciding bisimulation-like equivalences with finite-state processes ⋮ On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ A general approach to comparing infinite-state systems with their finite-state specifications ⋮ Basic process algebra with deadlocking states ⋮ A theory of structural stationarity in the \(\pi\)-calculus ⋮ Reachability is decidable for weakly extended process rewrite systems ⋮ Complexity Hierarchies beyond Elementary ⋮ On Model Checking Boolean BI ⋮ Decidability of bisimilarity for one-counter processes. ⋮ Branching place bisimilarity: a decidable behavioral equivalence for finite Petri nets with silent moves
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Modular construction and partial order semantics of Petri nets
- Decidability of a temporal logic problem for Petri nets
- Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
- Bisimulation and effectiveness
- On the reachability problem for 5-dimensional vector addition systems
- Petri nets and regular languages
- The equality problem for vector addition systems is undecidable
- A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
- Semigroups, Presburger formulas, and languages
- Parallel program schemata
- Rational sets in commutative monoids
- An Algorithm for the General Petri Net Reachability Problem
- High undecidability of weak bisimilarity for Petri nets
- Computability of Recursive Functions
