Abstract
Bisimulations enjoy numerous applications in the analysis of labeled transition systems. Many of these applications are based on two central observations: first, bisimilar systems satisfy the same branching-time properties; second, bisimilarity can be checked efficiently for finite-state systems. The local character of bisimulation, however, makes it difficult to address liveness concerns. Indeed, the definitions of fair bisimulation that have been proposed in the literature sacrifice locality, and with it, also efficient checkability. We put forward a new definition of fair bisimulation which does not suffer from this drawback.
The bisimilarity of two systems can be viewed in terms of a game played between a protagonist and an adversary. In each step of the infinite bisimulation game, the adversary chooses one system, makes a move, and the protagonist matches it with a move of the other system. Consistent with this game-based view, we call two fair transition systems bisimilar if in the bisimulation game, the infinite path produced in the first system is fair iff the infinite path produced in the second system is fair.
We show that this notion of fair bisimulation enjoys the following properties. First, fairly bisimilar systems satisfy the same formulas of the logics Fair-AFMC (the fair alternation-free μ-calculus) and Fair-CTL*. Therefore, fair bisimulations can serve as property-preserving abstractions for these logics and weaker ones, such as Fair-CTL and LTL. Indeed, Fair-AFMC provides an exact logical characterization of fair bisimilarity. Second, it can be checked in time polynomial in the number of states if two systems are fairly bisimilar. This is in stark contrast to all trace-based equivalences, which are traditionally used for addressing liveness but require exponential time for checking.
This research was supported in part by the DARPA (NASA) grant NAG2-1214, the SRC contract 99-TJ-683.003, the MARCO grant 98-DT-660, the DARPA (MARCO) grant MDA972-99-1-0001, and the NSF CAREER award CCR-9501708.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
ASB+94._A. Aziz, V. Singhal, F. Balarin, R.K. Brayton, and A.L. Sangiovanni-Vincentelli. Equivalences for fair kripke structures. In ICALP 94: Automata, Languages, and Programming, Lecture Notes in Computer Science 820, pages 364–375. Springer-Verlag, 1994. 300, 303, 304
M.C. Browne, E.M. Clarke, and O. Grumberg. Characterizing finite Kripke structures in propositional temporal logic. Theoretical Computer Science, 59:115–131, 1988. 303
J.A. Bergstra, J.W. Klop, and E.R. Olderog. Failures without chaos: a new process semantics for fair abstraction. In Formal Description Techniques III, pages 77–103. Elsevier, 1987. 301
J.C.M. Baeten and W.P. Weijland. Process Algebra. Cambridge University Press, 1990. 301
E.M. Clarke, E.A. Emerson, and A.P. Sistla. Automatic verification of finite-state concurrent systems using temporal-logic specifications. ACM Transactions on Programming Languages and Systems, 8(2):244–263, 1986. 303
R.J. Cleaveland, J. Parrow, and B. Steffen. The Concurrency Workbench: a semantics-based tool for the verification of finite-state systems. ACM Transactions on Programming Languages and Systems, 15(1):36–72, 1993. 300
W. Vogler, E. Brinksma, and A. Rensink. Fair testing. In CONCUR 95: Theories of Concurrency, Lecture Notes in Computer Science 962, pages 313–327. Springer-Verlag, July 1995. 301
O. Grumberg and D.E. Long. Model checking and modular verification. ACM Transactions on Programming Languages and Systems, 16(3):843–871, 1994. 300, 304
M.C.B. Hennessy. An algebraic theory of fair asynchronous communicating processes. Theretical Computer Science, 49:121–143, 1987. 301
M. Huth and M. Kwiatkowska. The semantics for fair recursion with divergence. Technical Report CSR-96-4, University of Birmingham, 1996. 301
T.A. Henzinger, O. Kupferman, and S. K. Rajamani. Fair simulation. In CONCUR 97: Theories of Concurrency, Lecture Notes in Computer Science 1243, pages 273–287. Springer-Verlag, July 1997. 300, 305, 307
P.C. Kanellakis and S.A. Smolka. CCS expressions, finite-state processes, and three problems of equivalence. Information and Computation, 86:43–68, 1990. 300
O. Kupferman and M.Y. Vardi. Verification of fair transition systems. In CAV 96: Computer Aided Verification, Lecture Notes in Computer Science 1102, pages 372–381. Springer-Verlag, 1996. 300, 304
O. Kupferman and M.Y. Vardi. Weak alternating automata and tree automata emptiness. In Proceedings of the 30th ACM Symposium on Theory of Computing, pages 224–233. ACM Press, 1998. 308
R. Milner. Communication and Concurrency. Prentice-Hall, 1989. 300, 302
V. Natarajan and R. Cleaveland. Divergence and fair testing. In ICALP 95: Automata, Languages, and Programming, Lecture Notes in Computer Science 944, pages 648–659. Springer-Verlag, 1995. 301
D.M.R. Park. Concurrency and Automata on Infinite Sequences. Lecture Notes in Computer Science 104. Springer-Verlag, 1980. 300, 302
R. Paige and R.E. Tarjan. Three partition-refinement algorithms. SIAM Journal of Computing, 16(6):973–989, 1987. 300, 303, 307
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Henzinger, T.A., Rajamani, S.K. (2000). Fair Bisimulation. In: Graf, S., Schwartzbach, M. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2000. Lecture Notes in Computer Science, vol 1785. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46419-0_21
Download citation
DOI: https://doi.org/10.1007/3-540-46419-0_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67282-1
Online ISBN: 978-3-540-46419-8
eBook Packages: Springer Book Archive