Ackermann Encoding, Bisimulations, and OBDDs

Title: Ackermann Encoding, Bisimulations, and OBDDs

Research Question: How can we efficiently represent and compute bisimulations for large graphs using Ackermann encoding and OBDDs?

Methodology: The researchers propose an alternative method to represent graphs using OBDDs (Binary Decision Diagrams). This method is based on partitioning the graph nodes and using a shared OBDD for each partition. They also present a method to compute bisimulations and represent them using OBDDs. This method is based on Ackermann encoding, which is an efficient way to represent hereditarily finite sets as OBDDs.

Results: The researchers show that their method can significantly reduce the size of the OBDDs needed to represent graphs, especially for large graphs. They also present a computation technique that can efficiently determine the bisimulation quotient using their proposed method.

Implications: The proposed method can lead to significant improvements in the efficiency of graph representation and bisimulation computation for large graphs. This can have a wide range of applications in various fields such as computer science, mathematics, and logic. The use of Ackermann encoding and OBDDs can also lead to more accurate and efficient results in these fields.

Link to Article: https://arxiv.org/abs/0311018v1 Authors: arXiv ID: 0311018v1