On the parallel complexity of bisimulation on finite systems

DOI10.4230/LIPICS.CSL.2016.12MaRDI QIDQ5278398zbMATH OpenFDO

Authors Moses Ganardi, Stefan Göller, Markus Lohrey

Publication date 19 July 2017

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2016.12

zbMATH Keywords

bisimulationcomputational complexitytree width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• scientific article; zbMATH DE number 6970796
• Deciding bisimilarity is P-complete
• scientific article; zbMATH DE number 1927588
• scientific article; zbMATH DE number 1670835
• scientific article; zbMATH DE number 1759489

Cited in

(8)

• Non-interleaving bisimulation equivalences on basic parallel processes
• Deciding bisimilarity is P-complete
• From bisimulation to simulation: Coarsest partition problems
• A comparison of succinctly represented finite-state systems
• scientific article; zbMATH DE number 1232246 (Why is no real title available?)
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• The Bisimulation Problem for Equational Graphs of Finite Out-Degree
• On the computational complexity of bisimulation, redux

This page was built for publication: On the parallel complexity of bisimulation on finite systems

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