Bisimilarity on basic parallel processes

DOI10.1016/j.tcs.2021.11.027OpenAlexW4200416319MaRDI QIDQ2072066

Petr Jančar

Publication date: 1 February 2022

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

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

zbMATH Keywords

verificationconcurrencyequivalence checkingbisimulation equivalencebasic parallel processes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Resource Bisimilarity in Petri Nets is Decidable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• CCS expressions, finite state processes, and three problems of equivalence
• Deciding bisimilarity is P-complete
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Process rewrite systems.
• BPA bisimilarity is EXPTIME-hard
• Decidability of branching bisimulation on normed commutative context-free processes
• Decidability of bisimulation equivalence for process generating context-free languages
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Three Partition Refinement Algorithms
• Branching time and abstraction in bisimulation semantics
• Branching Bisimilarity of Normed BPA Processes Is in NEXPTIME
• Branching Bisimilarity on Normed BPA Is EXPTIME-Complete
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
• Normed Processes, Unique Decomposition, and Complexity of Bisimulation Equivalences
• Checking Equality and Regularity for Normed BPA with Silent Moves

This page was built for publication: Bisimilarity on basic parallel processes