Simulazione (informatica)

Nell'informatica teorica una simulazione è una relazione tra sistemi a transizione di stati che associa sistemi che si comportano nella stessa maniera, nel senso che un sistema simula l'altro. Intuitivamente, un sistema simula un altro sistema se le sue mosse corrispondono a quelle del sistema simulato. La definizione di base mette in relazione stati all'interno di un sistema di transizioni ma questo è facilmente adattabile per mettere in relazione due sistemi separati costruendo un sistema che consista dell'unione disgiunta dei componenti corrispondenti.

Definizione formale

Dato un Sistema a transizioni di stati con etichette (S, Λ, →), per simulazione si intende una relazione binaria R su S (es. R ⊆ S×S) tale che per ogni p, q ∈ S, se Template:Tutto attaccato allora per ogni α ∈ Λ, e per ogni p' ∈ S,

$p\stackrel{\alpha }{\to }{p}^{\prime }$

implica che esiste un q' ∈ S tale che

$q\stackrel{\alpha }{\to }{q}^{\prime }$

e (p',q') ∈ R.

Voci correlate

• Bisimulazione