A Relation-Algebraic Theory of Bisimulations

• Autorzy: Winter M.
• Języki publikacji: EN

Abstrakty

EN

In this paper we develop an algebraic/categorical theory of bisimulations using relational methods. We define a general notion, which is capable of handeling different version of bisimilarity in a common context. Furthermore, the approach relates bisimulations with the notion of a covering known from the theory of graphs and their applications in topology and complex analysis.

Słowa kluczowe

EN

Dedekind categories; bisimulation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 4
• Strony: 429--449
• Opis fizyczny: bibliogr. 26 poz.

Twórcy

autor

Winter M.

• Department of Computer Science, Brock University St.Catharines, Ontario, Canada, L2S 3AI,

Bibliografia

• [1] Aceto L., Jeffrey A.: A complete axiomatization of timed bisimulation for a class of timed regular behaviours. TCS 152(2) (1995), 251-268.
• [2] Adamek J.: Introduction to Coalgebra. TAC 14 Vol. 8 (2005) 157-199
• [3] BerghammerR.: The RelView System. http://www. informatik. uni-kiel.de/^progsys/relview/
• [4] Bird R., de Moor O.: Algebra of Programming. Prentice Hall (1997).
• [5] Brown C, Hutton G.: Categories, allegories and circuit design. Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, LICS (1994) 372-381.
• [6] Castellani I.: Bisimulations and abstraction homomorphisms. In: Ehrig H., Floyd C, Nivat M., Thatcher J. (eds.) Proceedings TAPSOFT 85, LNCS 185 (1985) 223-238.
• [7] Castellani I., Hennessy M.: Distributed bisimulations. J. ACM 36(4) (1989), 887-911.
• [8] Chin L.H., Tarski A.: Distributive and modular laws in the arithmetic of relation algebras. University of California Press, Berkley and Los Angeles (1951)
• [9] Freyd P., Scedrov A.: Categories, Allegories. North-Holland (1990).
• [10] Gutierrez C: Decidability of the equational theory of allegories.
• [11] Larsen K. G., Skou A.: Bisimulation through probabilistic testing. Inf. Comput. 94(1) (1991), 1-28
• [12] Milner R.: Communication and Concurrency. Prentice Hall (1989)
• [13] Olivier J.P., Serrato D.: Categories de Dedekind. Morphismes dans les Categories de Schroder. C.R. Acad. Sci. Paris 290 (1980), 939-941.
• [14] Olivier J.P., Serrato D.: Squares and Rectangles in Relational Categories - Three Cases: Semilattice, Distributive lattice and Boolean Non-unitary. Fuzzy sets and systems 72 (1995), 167-178.
• [15] Rutten J.J.M.M.: Relators and Metric Bisimulations. Electr. Notes Theor. Comput. Sci. 11 (1998), 1-7.
• [16] Sangiorgi D.: On the Proof Method for Bisimulation (Extended Abstract). MFCS, LNCS 969 (1995), 479-488.
• [17] Schmidt G., Strohlein T.: Relationen und Graphen. Springer (1989); English version: Relations and Graphs. Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoret. Comput. Sci., Springer (1993)
• [18] Schmidt G., Hattensperger C, Winter M.: Heterogeneous Relation Algebras. In: Brink C, Kahl W., Schmidt G. (eds.), Relational Methods in Computer Science, Advances in Computer Science, Springer Vienna (1997).
• [19] Schmidt G.: Homomorphism and Isomorphism Theorems Generalized from a Relational Perspective, unpublished
• [20] E. Schroder, Algebra der Logik, 3. Band (Teubner, Leipzig, 1895).
• [21] A. Tarski, On the calculus of relations, J. Symbolic Logic 6 (1941) 73-89
• [22] Tarski A., Givant S.: A Formalization of Set Theory without Variables. AMS Coll. Pub. 41 (1987)
• [23] Winter M.: Strukturtheorie heterogener Relationenalgebren mit Anwendung auf Nichtdetermismus in Pro-grammiersprachen. Dissertationsverlag NG Kopierladen GmbH, Miinchen (1998)
• [24] Winter M., Kempf P,: Relational Semantics for Processes. In: Relational Methods for Computer Science Applications. Studies in Fuzzyness and Soft Computing. Physika Verlag Heidelberg (2001) 59-73
• [25] Winter M.: Decomposing Relations into Orderings. Relational and Kleene-Algebraic Methods in Computer Science, LNCS 3051, Springer (2004) 265-277
• [26] Winter M.: Goguen Categories - A Categorical Approach to L-fuzzy Relations, Trends in Logic Vol. 25, Springer (2007)