Bisimulation - AbsoluteAstronomy.com

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

a bisimulation is a binary relation

Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

between state transition system

State transition system

In theoretical computer science, a state transition system is an abstract machine used in the study of computation. The machine consists of a set of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition...

s, associating systems which behave in the same way in the sense that one system simulates the other and vice-versa.

Intuitively two systems are bisimilar if they match each other's moves. In this sense, each of the systems cannot be distinguished from the other by an observer.

Formal definition

Given a labelled state transition system

State transition system

(

, Λ, →), a bisimulation relation

Relation (mathematics)

In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...

is a binary relation

Binary relation

over

(i.e.,

⊆

) such that both

^-1 and

are simulation

Simulation preorder

In theoretical computer science a simulation preorder is a relation between state transition systems associating systems which behave in the same way in the sense that one system simulates the other....

s.

Equivalently

is a bisimulation if for every pair of elements

with

, for all α in Λ:

for all

implies that there is a

such that

and

;

and, symmetrically, for all

implies that there is a

such that

and

Given two states

and

is bisimilar to

, written

, if there is a bisimulation

such that

is in

.

The bisimilarity relation

is an equivalence relation

Equivalence relation

In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

. Furthermore, it is the largest bisimulation relation over a given transition system.

Note that it is not always the case that if

simulates

and

simulates

then they are bisimilar. For

and

to be bisimilar, the simulation between

and

must be the inverse

Binary relation

of the simulation between

and

. Counter-example (in CCS

Calculus of Communicating Systems

The Calculus of Communicating Systems is a process calculus introduced by Robin Milner around 1980 and the title of a book describing the calculus. Its actions model indivisible communications between exactly two participants. The formal language includes primitives for describing parallel...

, describing a coffee machine) :

and

simulate each other but are not bisimilar.

Relational definition

Bisimulation can be defined in terms of composition of relations

Composition of relations

In mathematics, the composition of binary relations is a concept of forming a new relation from two given relations R and S, having as its most well-known special case the composition of functions.- Definition :...

as follows.

Given a labelled state transition system

State transition system

, a bisimulation relation

Relation (mathematics)

In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...

is a binary relation

Binary relation

over

(i.e.,

⊆

) such that

and

From the monotonicity and continuity of relation composition, it follows immediately that the set of the bisimulations is closed under unions (joins in the poset of relations), and a simple algebraic calculation shows that the relation of bisimilarity—the join of all bisimulations—is an equivalence relation. This definition, and the associated treatment of bisimilarity, can be interpreted in any involutive quantale

Quantale

In mathematics, quantales are certain partially ordered algebraic structures that generalize locales as well as various multiplicative lattices of ideals from ring theory and functional analysis...

Fixpoint definition

Bisimilarity can also be defined in order theoretical

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

fashion, in terms of fixpoint theory, more precisely as the greatest fixed point of a certain function defined below.

Given a labelled state transition system

State transition system

(

, Λ, →), define

to be a function from binary relations over

to binary relations over

, as follows:

Let

be any binary relation over

is defined to be the set of all pairs

such that:

and

Bisimilarity is then defined to be the greatest fixed point of

Game theoretical definition

Bisimulation can also be thought of in terms of a game between two players: attacker and defender.

"Attacker" goes first and may choose any valid transition,

, from

. I.e.:

The "Defender" must then attempt to match that transition,

from either

depending on the attacker's move.
I.e., they must find an

such that:

Attacker and defender continue to take alternating turns until:

The defender is unable to find any valid transitions to match the attacker's move. In this case the attacker wins.
The game reaches states which are both 'dead' (i.e., there are no transitions from either state) In this case the defender wins
The game goes on forever, in which case the defender wins.
The game reaches states , which have already been visited. This is equivalent to an infinite play and counts as a win for the defender.

By the above definition the system is a bisimulation if and only if there exists a winning strategy for the defender.

Variants of bisimulation

In special contexts the notion of bisimulation is sometimes refined by adding additional requirements or constraints. For example if the state transition system includes a notion of silent (or internal) action, often denoted with

, i.e. actions which are not visible by external observers, then bisimulation can be relaxed to be weak bisimulation, in which if two states

and

are bisimilar and there is some number of internal actions leading from

to some state

then there must exist state

such that there is some number (possibly zero) of internal actions leading from

.

Typically, if the state transition system

State transition system

gives the operational semantics

Operational semantics

In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...

of a programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

, then the precise definition of bisimulation will be specific to the restrictions of the programming language. Therefore, in general, there may be more than one kind of bisimulation, (bisimilarity resp.) relationship depending on the context.

Bisimulation and modal logic

Since Kripke models

Kripke semantics

Kripke semantics is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke. It was first made for modal logics, and later adapted to intuitionistic logic and other non-classical systems...

are a special case of (labelled) state transition systems, bisimulation is also a topic in modal logic

Modal logic

Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...

. In fact, modal logic is the fragment of first-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

invariant under bisimulation (Van Benthem's theorem

Johan van Benthem (logician)

Johannes Franciscus Abraham Karel van Benthem is a University Professor of logic at the University of Amsterdam at the Institute for Logic, Language and Computation and professor of philosophy at Stanford University . He was awarded the Spinozapremie in 1996.He studied physics , philosophy...

Software tools

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Formal definition

Relational definition

Fixpoint definition

Game theoretical definition

Variants of bisimulation

Bisimulation and modal logic

See also

Software tools