Unifying Equivalences for Higher Dimensional Automata

• Autorzy: Oshevskaya E. , Virbitskaite I. , Best E.
• Języki publikacji: EN

Abstrakty

EN

The intention of the paper is to show how several categorical (open morphisms, path mor- phisms and coalgebraic morphisms based) approaches to an abstract characterization of bisimulation relate to each other and to behavioral bisimulations, in the setting of higher dimensional automata. Such a relating makes it possible to develop a metatheory designed for unified definition and study of equivalences in true concurrency semantics.

Słowa kluczowe

EN

high dimensional automata; bisimulation; open maps bisimulation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 119, nr 3/4
• Strony: 357--372
• Opis fizyczny: Bibliogr. 25 poz., wykr.

Twórcy

autor

Oshevskaya E.

autor

Virbitskaite I.

autor

Best E.

• A.P. Ershov Institute of Informatics Systems, SB RAS 6, Acad. Lavrentiev avenue, 630090, Novosibirsk, Russia,

Bibliografia

• [1] Aczel, P., Mendler, P. F.: A final coalgebra theorem. In: D. H. Pitt, D. E. Rydeheard, P. Dybjer, A. M. Pitts, A. Poign (eds.), CTCS, 1989. LNCS, vol. 389, Springer-Verlag, Berlin, 1989, 357-365.
• [2] Bednarczyk, M.A.: Hereditory history preserving bisimulation or what is the power of the future perfect in program logics. Technical Report, Polish Academy of Science (1991)
• [3] Cridlig, R.: Implementing a static analyzer of concurrent programs: Problems and perspectives. In: Dam, M. (ed.) LOMAPS Workshop 1996. LNCS, vol. 1192, pp. 244-259. Springer, Heidelberg (1997)
• [4] Fajstrup, L., Goubault, E., Raussen, M.: Detecting deadlocks in concurrent systems. In: Sangiorgi, D., de Simone, R. (eds.), CONCUR 1998. LNCS, vol. 1466, pp. 332-347. Springer, Heidelberg (1998)
• [5] Fahrenberg U.: A Category of Higher-Dimensional Automata. In: Sassone, V. (ed.), FOSSACS 2005. LNCS, vol. 3441, pp. 187-201. Springer, Heidelberg (2005)
• [6] Fröschle S., Lasota S.: Causality Versus True-Concurrency. Theoretical Computer Science 386(3): 169-187 (2007)
• [7] van Glabbeek, R.J.: Bisimulation semantics for higher dimensional automata, http://theory.stanford.edu/∼rvg/hda
• [8] van Glabbeek, R.J.: On the Expressiveness of higher dimensional automata. Theor. Comput. Sci. 356 (3), 265-290 (2006)
• [9] Goubault, E.: Domains of higher-dimensional automata. In: Best, E. (ed.) CONCUR 1993. LNCS, vol. 715, pp. 293-307. Springer, Heidelberg (1993)
• [10] Goubault, E.: A semantic view on distributed computability and complexity. In: 3rd Theory and Formal Methods Section Workshop. Imperial College Press, London (1996)
• [11] Goubault, E., Jensen, T.P.: Homology of higher-dimensional automata. In: Cleaveland, R. (ed.) CONCUR 1992. LNCS, vol. 630, pp. 254-268. Springer, Heidelberg (1992)
• [12] Herlihy, M., Shavit, N.: A simple constructive computability theorem for wait-free computation. In: 26th Annual ACM Symposium on Theory of Computing, pp. 243-252. ACM Press, New York (1994)
• [13] Herlihy, M., Rajsbaum, S.: New perspectives in distributed computing. In: Kutylowski, M., Pacholski, L., Wierzbicki, T. (eds.) MFCS 1999. LNCS, vol. 1672, pp. 170-186. Springer, Heidelberg (1999)
• [14] Joyal, A., Moerdijk, I.: A Completeness Theorem for Open Maps. Annals of Pure and Applied Logic, vol.70, pp. 51-86 (1994).
• [15] Jacobs, B., Hughes, J.: Simulations in coalgebra. Theoretical Computer Science, vol. 327(1-2), 2004, 71-108.
• [16] Joyal, A., Nielsen, M.,Winskel, G.: Bisimulation from open maps. Inform. Comput. 127(2), 164-185 (1996)
• [17] Lasota, S.: Coalgebra morphisms subsume open maps. Theoretical Computer Science, vol. 280, 2002, 123-135.
• [18] Monteiro, L.: A Coalgebraic Characterization of Behaviors in the Linear Time - Branching Time Spectrum. In: Andrea Corradini, Ugo Montanari (eds.), WADT'08, LNCS 5486, Springer-Verlag, Berlin, 2008, 251-265.
• [19] M. Nielsen, A. Cheng.: Observing behaviour categorically. In: Thiagarajan, P.S. (ed.) FST&TCS 1995. LNCS, vol. 1026, pp. 263-278. Springer, Heidelberg (1995)
• [20] Pratt, V.R.: Modeling concurrency with geometry. In: 18th Annual ACM Symposium on Principles of Programming Languages, pp. 311-322. ACM Press, New York (1991)
• [21] Roggenbach, M., Majster-Cederbaum, M.: Towards a unified view of bisimulation: a comparative study. Theoretical Computer Science, vol. 238, 2000, 81-130.
• [22] Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249, 3-80 (2000)
• [23] Sassone, V., Cattani, G.L.: Higher-dimensional transition systems. In: 11th Annual IEEE Symposium on Logic in Computer Science, pp. 55-62. IEEE Computer Society Press, Los Alamitos (1996)
• [24] Silva, A., Bonchi, F., Bonsangue, M., Rutten, J.: Generalizing the powerset construction, coalgebraically. In: Lodaya, K., Mahayan, M. (eds.) FSTTCS 2010. Leibniz. International Proceedings in Informatics (LIPIcs) Vol. 8, 2010
• [25] Virbitskaite, I.B., Gribovskaya, N.S., Best, E.: A Categorical View of Timed Behaviours. Fundam. Inform. 102(1), 2010, 129-143.