Strong bisimilarity of simple process algebras: Complexity lower bounds

DOI10.1007/S00236-003-0116-9MaRDI QIDQ1424356zbMATH OpenOpenAlexFDO

Authors Jiří Srba

Publication date 11 March 2004

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-003-0116-9

zbMATH Keywords

process rewrite systems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2086665
• Publication:4941915
• Normed processes, unique decomposition, and complexity of bisimulation equivalences
• Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof)
• On the complexity of bisimilarity for value-passing processes
• scientific article; zbMATH DE number 1670835
• Computable processes and bisimulation equivalence
• Publication:3028334
• A complexity analysis of bisimilarity for value-passing processes

Cited in

(14)

• Complexity of Weak Bisimilarity and Regularity for BPA and BPP
• scientific article; zbMATH DE number 2086665 (Why is no real title available?)
• Complexity of weak bisimilarity and regularity for BPA and BPP
• EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system
• A complexity analysis of bisimilarity for value-passing processes
• Normed processes, unique decomposition, and complexity of bisimulation equivalences
• Simulation preorder over simple process algebras
• scientific article; zbMATH DE number 1670835 (Why is no real title available?)
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• scientific article; zbMATH DE number 1232246 (Why is no real title available?)
• Resource Bisimilarity in Petri Nets is Decidable
• Convenient category of processes and simulations I: Modulo strong bisimilarity
• scientific article; zbMATH DE number 2086414 (Why is no real title available?)
• Bisimilarity on basic parallel processes

This page was built for publication: Strong bisimilarity of simple process algebras: Complexity lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1424356)