How to determine if a binary relation R on M is a bisimulation?

In summary, a binary relation R on a system M is considered a bisimulation if it is a subset of the ' operation, where for any two nodes a and b in M, a is related to b if and only if for all children x in a and children y in b, there exists a relationship between x and y. Additionally, the relation ~ on the class of all sets V is also a bisimulation if there exists an accessible pointed graph that is the picture of both a and b. An accessible pointed graph is a directed graph with a distinguished node from which all other nodes are connected by a path.
  • #1
Dragonfall
1,030
4
Let M be a system (possibly proper class-sized directed graph where the class of children of a given node is a set). A binary relation R on M is a BISIMULATION if [tex]R\subset R'[/tex], where for [tex]a, b\in M[/tex]

[tex]aR'b \Leftrightarrow ((\forall x \in a_M\exists y\in b_M xRy) \wedge (\forall x \in b_M\exists y\in a_M xRy))[/tex]

where [tex]a_M[/tex] is the set of children of a in M.

So let ~ be the relation on the class of all sets V such that a~b iff there exists an accessible pointed graph that is the picture of both a and b.

An accessible pointed graph is a directed graph with a distinguished node from where every other node is connected by a path.

Show that ~ is a bisimulation.

I'm not sure what bisimulation says. Can someone explain it in more familiar terms?
 
Physics news on Phys.org
  • #2
The wording above (quoted from the book) is very bad. It took me a long time to understand that R is a bisimulation if R is contained in the ' operation.
 

1. What is a binary relation?

A binary relation is a mathematical concept that represents a connection or relationship between two objects or elements in a set. It can be represented as a set of ordered pairs, where the first element in the pair is related to the second element.

2. What is a bisimulation?

A bisimulation is an equivalence relation between two systems that preserves the behavior of the systems. In other words, if two systems are bisimilar, they will produce the same results when given the same inputs. Bisimulation is commonly used in the study of concurrency and parallel computing.

3. How do you determine if a binary relation is a bisimulation?

To determine if a binary relation R on a set M is a bisimulation, you can use the following steps:

  • Check if R is an equivalence relation on M. This means that it must be reflexive, symmetric, and transitive.
  • For each pair of related elements (a,b) in R, check if all of the elements related to a are also related to b, and vice versa. This is known as the bisimulation property.
  • If both of these conditions are met, then R is a bisimulation on M.

4. What is the importance of determining if a binary relation is a bisimulation?

Determining if a binary relation is a bisimulation is important in the study of concurrency and parallel computing. It allows us to compare and analyze the behavior of different systems and identify any potential errors or discrepancies. It also helps in the design and verification of complex systems.

5. Can a binary relation be both a bisimulation and a partial ordering?

Yes, a binary relation can be both a bisimulation and a partial ordering. This means that it satisfies both the bisimulation property and the partial ordering properties of reflexivity, antisymmetry, and transitivity. A common example of such a relation is the subset relation, where two sets are bisimilar if and only if they are equal.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
763
  • Topology and Analysis
Replies
1
Views
939
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Back
Top