Deciding true concurrency equivalences on safe, finite nets

DOI10.1016/0304-3975(95)00132-8zbMath0877.68056OpenAlexW2003972637MaRDI QIDQ1365677

Albert R. Meyer, Lalita Jategaonkar

Publication date: 9 September 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00132-8

zbMATH Keywords

computational complexityPetri netsDEXPTIMEEXPSPACE

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (14)

The decidability border of hereditary history preserving bisimilarity ⋮ Minimal transition systems for history-preserving bisimulation ⋮ Causality, Behavioural Equivalences, and the Security of Cyberphysical Systems ⋮ Stochastic equivalence for performance analysis of concurrent systems in dtsiPBC ⋮ The complexity of PDL with interleaving ⋮ Undecidability of domino games and hhp-bisimilarity. ⋮ Decidability of Two Truly Concurrent Equivalences for Finite Bounded Petri Nets ⋮ Discrete time stochastic and deterministic Petri box calculus dtsdPBC ⋮ Hardness of preorder checking for basic formalisms ⋮ Complexity of Weak Bisimilarity and Regularity for BPA and BPP ⋮ Algorithms and Complexity of Automata Synthesis by Asynhcronous Orchestration With Applications to Web Services Composition ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Unnamed Item ⋮ Non-interleaving bisimulation equivalences on basic parallel processes

Cites Work

• Step failures semantics and a complete proof system
• Bisimulation and action refinement
• Failures semantics based on interval semiwords is a congruence for refinement
• CCS expressions, finite state processes, and three problems of equivalence
• Maximality preserving bisimulation
• Generalized OM-bisimulation
• Concurrent bisimulations in Petri nets
• A Theory of Communicating Sequential Processes
• Checking equivalences between concurrent systems of finite agents (Extended abstract)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding true concurrency equivalences on safe, finite nets