Why is simulation harder than bisimulation?

DOI10.1007/3-540-45694-5_39MaRDI QIDQ4484513zbMATH OpenFDO

Authors Antonin Kučera, Richard M. Mayr

Publication date 12 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2421/24210594.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Simulation preorder over simple process algebras
• scientific article; zbMATH DE number 6970796
• Deciding bisimilarity and similarity for probabilistic processes.
• Decision procedures and graph reductions for bisimulation equivalences part 1
• Simulation revisited

Cited in

(13)

• An efficient simulation algorithm based on abstract interpretation
• A comparison of succinctly represented finite-state systems
• scientific article; zbMATH DE number 1114007 (Why is no real title available?)
• The state explosion problem from trace to bisimulation equivalence
• Exploring the tractability border in epistemic tasks
• On the parallel complexity of bisimulation on finite systems
• Simulation relations and applications in formal methods
• The reachable simulation problem
• Coupled Similarity and Contrasimilarity, and How to Compute Them
• Computing reachable simulations on transition systems
• Generalizing the Paige-Tarjan algorithm by abstract interpretation
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
• EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system

This page was built for publication: Why is simulation harder than bisimulation?

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