Relation binaire entre états de systèmes à états (modèles de Kripke, systèmes de transitions étiquetés, processus) qui met en correspondance leur comportement observable pas à pas : chaque fois qu′un état relié effectue une transition étiquetée a, l′état lié peut correspondre par une transition a vers des états liés, et réciproquement ; la bisimilarité signifie l′existence d′une telle relation reliant les états.

Principe

Préserver l′indiscernabilité pour le langage d′observation choisi en exigeant un appariement réciproque des transitions (et des propriétés d′étiquetage), de sorte que les propriétés modales et invariantes par bisimulation ne distinguent pas des états bisimilaires.

Démonstration

Deux modèles de Kripke sont bisimilaires s′il existe une relation reliant leurs états initiaux telle que les valuations propositionnelles coïncident et que pour chaque successeur dans un modèle il existe un successeur correspondant dans l′autre ; toute formule modale vraie dans un état initial est vraie dans l′autre.

Mauvaise application

Utiliser la bisimulation de façon inexacte comme preuve d′équivalence pour des systèmes quantitatifs, probabilistes, temporisés ou sensibles aux ressources sans adopter les définitions appropriées de bisimulation quantitative ou probabiliste ; ou conclure à l′isomorphisme à partir de la bisimilarité en présence de distinctions de bisimulation de branchement.

Conséquence

La bisimulation fournit une équivalence comportementale garantissant l′invariance des formules modales et de nombreux langages de spécification ; elle permet la minimisation et la quotientation des modèles, le raisonnement par congruence dans les calculs de processus et des techniques de vérification compositionnelle.

Inversion

Inverser la relation conduit à la simulation : une relation de simulation exige seulement un appariement unilatéral (un système simule un autre) et donne un préordre plutôt qu′une équivalence ; cette inversion met en évidence les raffinements observables plutôt que l′identité comportementale complète.

Limite

La bisimulation standard s′applique aux systèmes de transitions étiquetés et aux cadres de Kripke avec observations booléennes ; elle doit être adaptée pour les systèmes probabilistes, stochastiques, temporisés, hybrides ou quantitatifs, et elle se focalise sur la structure de branchement plutôt que sur l′équivalence de traces linéaires.

Tension sémantique

La tension apparaît entre bisimulation et équivalence de traces : l′équivalence de traces ignore la structure de branchement et est plus faible, tandis que la bisimulation est plus forte mais parfois trop discriminante pour des spécifications observationnelles ; il existe aussi une tension entre la bisimulation forte et des notions plus faibles (branching, weak, observational) qui abstraient les pas internes.

Synthèse

La Bisimulation est la relation d′appariement réciproque pas à pas qui capture l′indiscernabilité comportementale dans les modèles branchés : en imposant l′appariement symétrique des mouvements et des observations, elle fonde l′invariance modale, la réduction de modèles et le raisonnement compositionnel, avec des variantes adaptées aux caractéristiques quantitatives des systèmes.