Deciding true concurrency equivalences on safe, finite nets

DOI10.1016/0304-3975(95)00132-8zbMath0877.68056MaRDI 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 complexity; Petri nets; DEXPTIME; EXPSPACE

Mathematics Subject Classification ID

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

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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

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