The state explosion problem from trace to bisimulation equivalence

DOI10.1007/3-540-46432-8_13MaRDI QIDQ4508303zbMATH OpenFDO

Authors François Laroussinie, Philippe Schnoebelen

Publication date 3 October 2000

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

Full work available at URL https://doi.org/10.1007/3-540-46432-8_13

zbMATH Keywords

bisimilaritysimulation preorder

Mathematics Subject Classification ID

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

Recommendations

• Hardness of equivalence checking for composed finite-state systems
• Behavioural equivalences on finite-state systems are PTIME-hard
• scientific article; zbMATH DE number 1927588
• Equivalence checking of non-flat systems is EXPTIME-hard.
• scientific article; zbMATH DE number 2102770

Cited in

(15)

• Hardness of equivalence checking for composed finite-state systems
• Is your model checker on time? On the complexity of model checking for timed modal logics
• A complete normal-form bisimilarity for state
• A parametric analysis of the state-explosion problem in model checking
• Characteristic formulae for timed autoamta
• Keeping secrets in resource aware components
• A comparison of succinctly represented finite-state systems
• Hardness of preorder checking for basic formalisms
• Behavioural equivalences on finite-state systems are PTIME-hard
• Better abstractions for timed automata
• Equivalence checking of non-flat systems is EXPTIME-hard.
• Hardness of preorder checking for basic formalisms
• On timed alternating simulation for concurrent timed games
• State explosion in almost-sure probabilistic reachability
• EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system

This page was built for publication: The state explosion problem from trace to bisimulation equivalence

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