Préordre de simulation

Préordre de simulation

En informatique théorique un préordre de simulation est une relation entre systèmes de transition d'états associant des systèmes qui se comportent de la même façon au sens qu'un système simule l'autre.

Intuitivement, un système simule l'autre s'il peut imiter toutes ses actions.

La définition basique relie les états à l'intérieur d'un système de transition, mais c'est facilement adaptable pour mettre en relation deux systèmes de transition séparés en construisant un système consistant en l'union disjointe des composants correspondants.

Définition formelle

Étant donné un système de transition d'états étiqueté (S, Λ, →), une relation de simulation est une relation binaire R sur S (c.à.d R ⊆ S × S) telle que pour chaque paire d'éléments p, q ∈ S, si (p,q)∈ R alors pour tout α ∈ Λ, et pour tout p' ∈ S,

\begin{matrix} & \alpha & \\ p & \rightarrow & p' \\ \end{matrix}

implique qu'il existe q' ∈ S tel que

\begin{matrix} & \alpha & \\ q & \rightarrow & q' \\ \end{matrix}

et (p',q') ∈ R.

Étant donnés deux états p et q dans S, q simule p, noté p ≤ q s'il existe une simulation R telle que (p, q) ∈ R. Dans ce cas, p et q sont dits similaires et ≤ est appelé la relation de similarité.

La relation de similarité ≤ est un pré-ordre. De plus, c'est la plus grande simulation sur un système de transition donné.

Similarité de systèmes de transition séparés

Quand on compare deux systèmes de transition différents (S', Λ', →') et (S' ', Λ' ', →' '), les notions basiques de simulation et de similarité peuvent être utilisées en formant la composition disjointe des deux machines, (S, Λ, →) avec S = S' ∪ S' ', Λ = Λ' ∪ Λ' ' et → = →' ∪ →' ', où ∪ est l'opérateur d'union disjointe entre ensembles.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Préordre de simulation de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Preordre de simulation — Préordre de simulation En informatique théorique un préordre de simulation est une relation entre systèmes de transition d états associant des systèmes qui se comportent de la même façon au sens qu un système simule l autre. Intuitivement, un… …   Wikipédia en Français

  • Simulation — Sur les autres projets Wikimedia : « Simulation », sur le Wiktionnaire (dictionnaire universel) Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Simulation de phénomènes réels Kriegspiel,… …   Wikipédia en Français

  • Pré-ordre de simulation — Préordre de simulation En informatique théorique un préordre de simulation est une relation entre systèmes de transition d états associant des systèmes qui se comportent de la même façon au sens qu un système simule l autre. Intuitivement, un… …   Wikipédia en Français

  • Simuler — Simulation Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Simulé — Simulation Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Bisimulation — En informatique théorique une bisimulation est une relation binaire entre systèmes de transition d états, 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… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”