Server : Apache System : Linux webd348.cluster026.gra.hosting.ovh.net 5.15.148-ovh-vps-grsec-zfs-classid #1 SMP Thu Feb 8 09:41:04 UTC 2024 x86_64 User : hednacluml ( 122243) PHP Version : 8.3.9 Disable Function : _dyuweyrj4,_dyuweyrj4r,dl Directory : /home/hednacluml/encyclo/articles/b/i/s/ |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr" lang="fr" dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<!-- headlinks removed -->
<link rel="shortcut icon" href="../../../../misc/favicon.ico"/>
<title>Bisimulation - Wikipédia</title>
<style type="text/css">/*<![CDATA[*/ @import "../../../../skins/offline/main.css"; /*]]>*/</style>
<link rel="stylesheet" type="text/css" media="print" href="../../../../skins/common/commonPrint.css" />
<!--[if lt IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE50Fixes.css";</style><![endif]-->
<!--[if IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE55Fixes.css";</style><![endif]-->
<!--[if IE 6]><style type="text/css">@import "../../../../skins/monobook/IE60Fixes.css";</style><![endif]-->
<!--[if IE]><script type="text/javascript" src="../../../../skins/common/IEFixes.js"></script>
<meta http-equiv="imagetoolbar" content="no" /><![endif]-->
<script type="text/javascript" src="../../../../skins/common/wikibits.js"></script>
<script type="text/javascript" src="../../../../skins/offline/md5.js"></script>
<script type="text/javascript" src="../../../../skins/offline/utf8.js"></script>
<script type="text/javascript" src="../../../../skins/offline/lookup.js"></script>
<script type="text/javascript" src="../../../../raw/gen.js"></script> <style type="text/css">/*<![CDATA[*/
@import "../../../../raw/MediaWiki%7ECommon.css";
@import "../../../../raw/MediaWiki%7EMonobook.css";
@import "../../../../raw/gen.css";
/*]]>*/</style> </head>
<body
class="ns-0">
<div id="globalWrapper">
<div id="column-content">
<div id="content">
<a name="top" id="contentTop"></a>
<h1 class="firstHeading">Bisimulation</h1>
<div id="bodyContent">
<h3 id="siteSub">Un article de Wikipédia, l'encyclopédie libre.</h3>
<div id="contentSub"></div>
<!-- start content -->
<p>En <a href="../../../../articles/i/n/f/Informatique_th%C3%A9orique.html" title="Informatique théorique">informatique théorique</a> une <b>bisimulation</b> est une <a href="../../../../articles/r/e/l/Relation_binaire.html" title="Relation binaire">relation binaire</a> entre <a href="../../../../articles/s/y/s/Syst%C3%A8me_de_transition_d%27%C3%A9tats.html" title="Système de transition d'états">systèmes de transition d'états</a>, associant les systèmes qui se comportent de la même façon au sens qu'un des systèmes simule l'autre et vice-versa. Une bisimulation sur un même système n'est pas nécessairement une relation d'équivalence, elle n'est même pas nécessairement réflexive.</p>
<p>Intuitivement deux systèmes sont bisimilaires s'ils sont capables de s'imiter l'un l'autre. Dans cette optique, chaque système ne peut être distingué de l'autre par un observateur.</p>
<table id="toc" class="toc" summary="Sommaire">
<tr>
<td>
<div id="toctitle">
<h2>Sommaire</h2>
</div>
<ul>
<li class="toclevel-1"><a href="#D.C3.A9finition_formelle"><span class="tocnumber">1</span> <span class="toctext">Définition formelle</span></a></li>
<li class="toclevel-1"><a href="#Variantes_de_la_bisimulation"><span class="tocnumber">2</span> <span class="toctext">Variantes de la bisimulation</span></a></li>
<li class="toclevel-1"><a href="#Voir_aussi"><span class="tocnumber">3</span> <span class="toctext">Voir aussi</span></a></li>
<li class="toclevel-1"><a href="#R.C3.A9f.C3.A9rences"><span class="tocnumber">4</span> <span class="toctext">Références</span></a></li>
</ul>
</td>
</tr>
</table>
<script type="text/javascript">
//<![CDATA[
if (window.showTocToggle) { var tocShowText = "afficher"; var tocHideText = "masquer"; showTocToggle(); }
//]]>
</script>
<p><a name="D.C3.A9finition_formelle" id="D.C3.A9finition_formelle"></a></p>
<h2><span class="editsection">[<a href="../../../../articles/b/i/s/Bisimulation.html" title="Modifier la section : Définition formelle">modifier</a>]</span> <span class="mw-headline">Définition formelle</span></h2>
<p>Étant donné un <a href="../../../../articles/s/y/s/Syst%C3%A8me_de_transition_d%27%C3%A9tats.html" title="Système de transition d'états">système de transition d'états</a> étiqueté (S, Λ, →), une <a href="../../../../articles/c/o/r/Correspondance_et_relation.html" title="Correspondance et relation">relation</a> de <i>bisimulation</i> est une <a href="../../../../articles/r/e/l/Relation_binaire.html" title="Relation binaire">relation binaire</a> R sur S (c.à.d R ⊆ S × S) telle que à la fois R et R<sup>-1</sup> sont des <a href="../../../../articles/p/r/%C3%A9/Pr%C3%A9ordre_de_simulation.html" title="Préordre de simulation">préordres de simulation</a>.</p>
<p>De façon équivalente R est une bisimulation si pour chaque paire d'éléments p, q dans S, si (p,q) est dans R alors pour tout α dans Λ, et pour tout p' dans S,</p>
<dl>
<dd><img class="tex" alt="
p\ \stackrel{\alpha}{\rightarrow}\ p'
" src="../../../../math/5/f/1/5f1be436397378ab6202f5261310b294.png" /></dd>
</dl>
<p>implique qu'il existe un q' dans S tel que</p>
<dl>
<dd><img class="tex" alt="
q\ \stackrel{\alpha}{\rightarrow}\ q'
" src="../../../../math/3/4/7/347b62be8d73a27983a0491786f932bd.png" /></dd>
</dl>
<p>et (p',q') dans R, et pour tout q' dans S,</p>
<dl>
<dd><img class="tex" alt="
q\ \stackrel{\alpha}{\rightarrow}\ q'
" src="../../../../math/3/4/7/347b62be8d73a27983a0491786f932bd.png" /></dd>
</dl>
<p>implique qu'il existe un p' dans S tel que</p>
<dl>
<dd><img class="tex" alt="
p\ \stackrel{\alpha}{\rightarrow}\ p'
" src="../../../../math/5/f/1/5f1be436397378ab6202f5261310b294.png" /></dd>
</dl>
<p>et (p',q') dans R.</p>
<p>Étant donnés deux états p et q dans S, p est <b>bisimilaire</b> à q, noté p ∼ q, s'il existe une bisimulation R telle que (p, q) soit dans R.</p>
<p>La relation de bisimilarité ∼ est une <a href="../../../../articles/r/e/l/Relation_d%27%C3%A9quivalence.html" title="Relation d'équivalence">relation d'équivalence</a>. De plus, c'est la plus grande relation de bisimulation sur un système de transition donné.</p>
<p>Le fait que p simule q et q simule p ne suffit pas toujours pour qu'ils soient bisimilaires. Pour que p et q soient bisimilaires, la simulation entre p et q doit être l'<a href="../../../../articles/r/e/l/Relation_binaire.html" title="Relation binaire">inverse</a> de la simulation entre q et p.</p>
<p><a name="Variantes_de_la_bisimulation" id="Variantes_de_la_bisimulation"></a></p>
<h2><span class="editsection">[<a href="../../../../articles/b/i/s/Bisimulation.html" title="Modifier la section : Variantes de la bisimulation">modifier</a>]</span> <span class="mw-headline">Variantes de la bisimulation</span></h2>
<p>Dans des contextes particuliers la notion de bisimulation est parfois raffinée en ajoutant des contraintes supplémentaires. Par exemple si le système de transition d'états inclut une notion d'<i>actions silencieuses</i>, souvent dénotées par <a href="../../../../articles/%CF%84/_/_/%CE%A4.html" class="mw-redirect" title="Τ">τ</a>, c.à.d. des actions qui ne sont pas visibles par les observateurs externes, alors la bisimulation peut être affaiblie pour devenir la <i>bisimulation faible</i>, dans laquelle les actions silencieuses sont ignorées.</p>
<p>Typiquement, si le <a href="../../../../articles/s/y/s/Syst%C3%A8me_de_transition_d%27%C3%A9tats.html" title="Système de transition d'états">système de transition d'états</a> donne la <a href="../../../../articles/s/%C3%A9/m/S%C3%A9mantique_op%C3%A9rationnelle.html" title="Sémantique opérationnelle">sémantique opérationnelle</a> d'un <a href="../../../../articles/l/a/n/Langage_de_programmation.html" title="Langage de programmation">langage de programmation</a>, alors la définition précise de la bisimulation sera spécifique aux restrictions du langage de programmation. Par conséquent, en général, il peut y avoir plus d'une sorte de relation de bisimulation (resp. bisimilarité) en fonction du contexte.</p>
<p><a name="Voir_aussi" id="Voir_aussi"></a></p>
<h2><span class="editsection">[<a href="../../../../articles/b/i/s/Bisimulation.html" title="Modifier la section : Voir aussi">modifier</a>]</span> <span class="mw-headline">Voir aussi</span></h2>
<ul>
<li><a href="../../../../articles/s/%C3%A9/m/S%C3%A9mantique_op%C3%A9rationnelle.html" title="Sémantique opérationnelle">Sémantique opérationnelle</a></li>
<li><a href="../../../../articles/s/y/s/Syst%C3%A8me_de_transition_d%27%C3%A9tats.html" title="Système de transition d'états">Système de transition d'états</a></li>
<li><a href="../../../../articles/p/r/%C3%A9/Pr%C3%A9ordre_de_simulation.html" title="Préordre de simulation">Préordre de simulation</a></li>
<li><a href="../../../../articles/c/o/n/Congruence.html" title="Congruence">Congruence</a></li>
</ul>
<p><a name="R.C3.A9f.C3.A9rences" id="R.C3.A9f.C3.A9rences"></a></p>
<h2><span class="editsection">[<a href="../../../../articles/b/i/s/Bisimulation.html" title="Modifier la section : Références">modifier</a>]</span> <span class="mw-headline">Références</span></h2>
<ul>
<li><span style="cursor:help;font-family:monospace;font-weight:bold;font-size:small" title="Langue : anglais">(en)</span> Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en <a href="../../../../articles/a/n/g/Anglais.html" title="Anglais">anglais</a> intitulé « <i><span class="plainlinks"><a href="http://en.wikipedia.org../../../../articles/b/i/s/Bisimulation.html" class="external text" title="http://en.wikipedia.org../../../../articles/b/i/s/Bisimulation.html" rel="nofollow">Bisimulation</a></span></i> ».</li>
</ul>
<ul id="bandeau-portail" class="bandeau-portail">
<li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><a href="../../../../articles/c/r/y/Image%7ECrystal_mycomputer.png_ff1d.html" class="image" title="Icône du portail de l’informatique"><img alt="Icône du portail de l’informatique" src="../../../../images/shared/thumb/e/e3/Crystal_mycomputer.png/24px-Crystal_mycomputer.png" width="24" height="24" border="0" /></a></span> <span class="bandeau-portail-texte"><a href="../../../../articles/i/n/f/Portail%7EInformatique_2d39.html" title="Portail:Informatique">Portail de l’informatique</a></span></span></li>
<li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><a href="../../../../articles/r/a/c/Image%7ERacine_carr%C3%A9e_bleue.svg_2864.html" class="image" title="Icône du portail des mathématiques"><img alt="Icône du portail des mathématiques" src="../../../../images/shared/thumb/1/1f/Racine_carrée_bleue.svg/24px-Racine_carrée_bleue.svg.png" width="24" height="24" border="0" /></a></span> <span class="bandeau-portail-texte"><a href="../../../../articles/m/a/t/Portail%7EMath%C3%A9matiques_0c04.html" title="Portail:Mathématiques">Portail des mathématiques</a></span></span></li>
</ul>
<!--
NewPP limit report
Preprocessor node count: 185/1000000
Post-expand include size: 3330/2048000 bytes
Template argument size: 321/2048000 bytes
Expensive parser function count: 0/500
-->
<div class="printfooter">
</div>
<div id="catlinks"><div id='catlinks' class='catlinks'><div id="mw-normal-catlinks"><a href="../../../../articles/a/c/c/Cat%C3%A9gorie%7EAccueil_1aae.html" title="Catégorie:Accueil">Catégories</a> : <span dir='ltr'><a href="../../../../articles/i/n/f/Cat%C3%A9gorie%7EInformatique_th%C3%A9orique_644b.html" title="Catégorie:Informatique théorique">Informatique théorique</a></span> | <span dir='ltr'><a href="../../../../articles/l/o/g/Cat%C3%A9gorie%7ELogique_af7a.html" title="Catégorie:Logique">Logique</a></span> | <span dir='ltr'><a href="../../../../articles/m/%C3%A9/t/Cat%C3%A9gorie%7EM%C3%A9thode_formelle_2d3b.html" title="Catégorie:Méthode formelle">Méthode formelle</a></span></div></div></div> <!-- end content -->
<div class="visualClear"></div>
</div>
</div>
</div>
<div id="column-one">
<div id="p-cactions" class="portlet">
<h5>Views</h5>
<ul>
<li id="ca-nstab-main"
class="selected" ><a href="../../../../articles/b/i/s/Bisimulation.html">Article</a></li><li id="ca-talk"
><a href="../../../../articles/b/i/s/Discuter%7EBisimulation_e769.html">Discussion</a></li><li id="ca-current"
><a href="http://fr.wikipedia.org/wiki/Bisimulation">Version actuelle</a></li> </ul>
</div>
<div class="portlet" id="p-logo">
<a style="background-image: url(../../../../misc/Wiki.png);"
href="../../../../index.html"
title="Accueil"></a>
</div>
<script type="text/javascript"> if (window.isMSIE55) fixalpha(); </script>
<div class='portlet' id='p-navigation'>
<h5>Navigation</h5>
<div class='pBody'>
<ul>
<li id="n-mainpage"><a href="../../../../index.html">Accueil</a></li>
<li id="n-thema"><a href="../../../../articles/a/c/c/Portail%7EAccueil_bcc9.html">Portails thématiques</a></li>
<li id="n-alphindex"><a href="../../../../articles/t/o/u/Special%7EToutes_les_pages_fabc.html">Index alphabétique</a></li>
<li id="n-randompage"><a href="../../../../articles/p/a/g/Special%7EPage_au_hasard_9c81.html">Un article au hasard</a></li>
<li id="n-contact"><a href="../../../../articles/c/o/n/Wikip%C3%A9dia%7EContact_929e.html">Contacter Wikipédia</a></li>
</ul>
</div>
</div>
<div class='portlet' id='p-Contribuer'>
<h5>Contribuer</h5>
<div class='pBody'>
<ul>
<li id="n-help"><a href="../../../../articles/s/o/m/Aide%7ESommaire_c9f0.html">Aide</a></li>
<li id="n-portal"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_5272.html">Communauté</a></li>
<li id="n-recentchanges"><a href="../../../../articles/m/o/d/Special%7EModifications_r%C3%A9centes_b222.html">Modifications récentes</a></li>
<li id="n-aboutwp"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_des_nouveaux_arrivants_0784.html">Accueil des nouveaux arrivants</a></li>
<li id="n-sitesupport"><a href="http://meta.wikimedia.org/wiki/Faire_un_don:_explication">Faire un don</a></li>
</ul>
</div>
</div>
<div id="p-search" class="portlet">
<h5><label for="searchInput">Rechercher</label></h5>
<div id="searchBody" class="pBody">
<form action="javascript:goToStatic(3)" id="searchform"><div>
<input id="searchInput" name="search" type="text"
accesskey="C" value="" />
<input type='submit' name="go" class="searchButton" id="searchGoButton"
value="Aller" />
</div></form>
</div>
</div>
<div id="p-lang" class="portlet">
<h5>Autres langues</h5>
<div class="pBody">
<ul>
<li>
<a href="../../../../../cs/articles/b/i/s/Bisimulace.html">Česky</a>
</li>
<li>
<a href="../../../../../de/articles/b/i/s/Bisimulation.html">Deutsch</a>
</li>
<li>
<a href="../../../../../en/articles/b/i/s/Bisimulation.html">English</a>
</li>
<li>
<a href="../../../../../ja/articles/%E5%8F%8C/%E6%A8%A1/%E5%80%A3/%E5%8F%8C%E6%A8%A1%E5%80%A3%E6%80%A7.html">日本語</a>
</li>
</ul>
</div>
</div>
</div><!-- end of the left (by default at least) column -->
<div class="visualClear"></div>
<div id="footer">
<div id="f-poweredbyico"><a href="http://www.mediawiki.org/"><img src="../../../../skins/common/images/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" /></a></div> <div id="f-copyrightico"><a href="http://wikimediafoundation.org/"><img src="../../../../misc/wikimedia-button.png" border="0" alt="Wikimedia Foundation"/></a></div> <ul id="f-list">
<li id="f-credits">Cette page a été modifiée pour la dernière fois le 11 juin 2008 à 02:16 par Utilisateur <a href="../../../../articles/b/a/n/Utilisateur%7EBan_e699.html" title="Utilisateur:Ban">Ban</a>. Basé sur le travail de Utilisateur(s) <a href="../../../../articles/s/h/e/Utilisateur%7ESherbrooke_9f52.html" title="Utilisateur:Sherbrooke">Sherbrooke</a>, <a href="../../../../articles/b/a/d/Utilisateur%7EBadmood_4dbf.html" title="Utilisateur:Badmood">Badmood</a>, <a href="../../../../articles/g/o/d/Utilisateur%7EGodix_3396.html" title="Utilisateur:Godix">Godix</a>, <a href="../../../../articles/o/u/t/Utilisateur%7EOuts_7cbf.html" title="Utilisateur:Outs">Outs</a>, <a href="../../../../articles/j/e/f/Utilisateur%7EJef-Infojef_b31d.html" title="Utilisateur:Jef-Infojef">Jef-Infojef</a>, <a href="../../../../articles/j/a/n/Utilisateur%7EJAnDbot_ea65.html" title="Utilisateur:JAnDbot">JAnDbot</a>, <a href="../../../../articles/m/e/d/Utilisateur%7EMedBot_8f10.html" title="Utilisateur:MedBot">MedBot</a>, <a href="../../../../articles/c/h/r/Utilisateur%7EChris93_f10d.html" title="Utilisateur:Chris93">Chris93</a>, <a href="../../../../articles/s/e/b/Utilisateur%7ESebfun_250a.html" title="Utilisateur:Sebfun">Sebfun</a> et <a href="../../../../articles/j/a/b/Utilisateur%7EJabial_0fcc.html" title="Utilisateur:Jabial">Jabial</a> et Utilisateur(s) non enregistré(s) de Wikipédia.</li> <li id="f-copyright"><span style="white-space:normal"><a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Droit_d'auteur" title="Droit d'auteur">Droit d'auteur</a> : Tous les textes sont disponibles sous les termes de la <a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Licence_de_documentation_libre_GNU" title="GFDL">licence de documentation libre GNU</a> (GFDL).<br/>
Wikipedia® est une marque déposée de la <a href="http://wikimediafoundation.org/wiki/Accueil" title="Wikimedia Foundation">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a class="internal" href="http://en.wikipedia.org/wiki/501(c)" title="501(c)">501(c)(3)</a> du code fiscal des États-Unis.</span><br/></li> <li id="f-about"><a href="../../../../articles/%C3%A0/_/p/Wikip%C3%A9dia%7E%C3%80_propos_5de1.html" title="Wikipédia:À propos">À propos de Wikipédia</a></li> <li id="f-disclaimer"><a href="../../../../articles/a/v/e/Wikip%C3%A9dia%7EAvertissements_g%C3%A9n%C3%A9raux_fef1.html" title="Wikipédia:Avertissements généraux">Avertissements</a></li> </ul>
</div>
</div>
</body>
</html>