Approximate reachability and bisimulation equivalences for transition systems

Abstract

Using Baire metric, this paper proposes a generalized framework of transition system approximation by developing the notions of approximate reachability and approximate bisimulation equivalences. The proposed framework captures the traditional exact equivalence as a special case. Approximate reachability equivalence is coarser than approximate bisimulation equivalence, just like the hierarchy of the exact ones. Both approximate equivalences satisfy the transitive property, consequently, they can be used in transition system approximation.

Keywords

approximate equivalence / reachability / bisimulation / transition system

References

[1] van Glabbeek R J. The linear time-branching time spectrum i-The semantics of concrete, sequential processes. Handbook of Process Algebra[M], 2001, Amsterdam, the Netherlands: Elsevier Science.

[2] Fuhrmann P A, Helmke U. Reachability, observability and strict equivalence of networks of linear systems[J]. Mathematics of Control, Signals, and Systems, 2013, 25(4): 437-471.

[3] Churchill M, Mosses P D. Modular bisimulation theory for computations and values. Foundations of Software Science and Computation Structures[M], 2013, Germany: Springer Berlin Heidelberg.

[4] Ciric M, Ignjatovic J, Basic M, et al. Nondeterministic automata: Equivalence, bisimulations, and uniform relations[J]. Information Sciences, 2014, 261: 185-218.

[5] van Breugel F. An introduction to metric semantics: Operational and denotational models for programming and specification languages[J]. Theoretical Computer Science, 2001, 258(1/2): 1-98.

[6] Klin B, Sassone V. Structural operational semantics for stochastic and weighted transition systems[J]. Information and Computation, 2013, 227: 58-83.

[7] Girard A, Pappas G J. Approximation metrics for discrete and continuous systems[J]. IEEE Transactions on Automatic Control, 2007, 52(5): 782-798.

[8] Baire R. The representation of discontinuous function[J]. Acta Mathematica, 1906, 30(1): 1-48.

[9] Cao Y Z, Ying M. Similarity-based supervisory control of discrete-event systems[J]. IEEE Transactions on Automatic Control, 2006, 51(2): 325-330.

[10] Cao Y Z, Chen G Q. Towards approximate equivalences of workflow processes[C]. Proceedings of the 1st International Conference on E-Business Intelligence (ICEBI2010). Kunming, China, 2010.

[11] Yang H, Jiang B, Cocquempot V. Fault tolerant control and hybrid systems. Fault Tolerant Control Design for Hybrid Systems[M], 2010, Germany: Springer-Verlag Berlin Heidelberg

[12] Girard A, Julius A A, Pappas G J. Approximate simulation relations for hybrid systems[J]. Discrete Event Dynamic Systems, 2008, 18(2): 163-179.

[13] Girard A, Pappas G J. Approximate bisimulation: A bridge between computer science and control theory[J]. European Journal of Control, 2011, 17(5/6): 568-578.

[14] Julius A A, D’Innocenzo A, Di Benedetto M D, et al. Approximate equivalence and synchronization of metric transition systems[J]. Systems & Control Letters, 2009, 58(2): 94-101.