Coalgebras for modelling observable behaviour of programs

• Autorzy: Steingartner W. , Novitzka V.

Identyfikatory

DOI

10.17512/jamcm.2017.2.12

• Języki publikacji: EN

Abstrakty

EN

A useful tool for modelling behaviour in theoretical computer science is the concept of coalgebras. Coalgebras enable one to model execution of programs step by step using categorical structures and polynomial endofunctors. In our paper, we start with a short introduction of basic notions and we use this method for modelling structural operational semantics of a simple imperative language.

Słowa kluczowe

EN

category; coalgebra; observable behaviour; polynomial endofunctor; semantics

PL

coalgebra; endofunktor; zachowanie programów

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Journal of Applied Mathematics and Computational Mechanics
• Rocznik: 2017
• Tom: Vol. 16, nr 2
• Strony: 145--157
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Steingartner W.

• Faculty of Electrical Engineering and Informatics, Technical University of Košice

autor

Novitzka V.

• Faculty of Electrical Engineering and Informatics, Technical University of Košice Slovakia

Bibliografia

• [1] Novitzká V., Mihályi D., Steingartner W., Coalgebraic behaviour of algebraic programs, Analele Universitatii din Oradea, Proc. 8th International Conference on Engineering of Modern Electric Systems,University of Oradea, Romania 2007, 9, 60-64.
• [2] Rutten J., Universal Coalgebra: A Theory of Systems, Technical Report CS-R9652, CWI, Amsterdam 1996.
• [3] Jacobs B., Introduction to Coalgebra, Towards Mathematics of States and Observations, Version 2.0, 2012.
• [4] Reichel H., Behavioural equivalence - a unifying concept for initial and final specifications, 3rd Hungarian Computer Science Conference, Akadémia kiadó, 3, 1981.
• [5] Gumm P., Elements of the General Theory of Coalgebras, Notes of Lecture given at LUATCS’99: Logic, Universal Algebra, Theoretical Computer Science, Johanesburg 1999.
• [6] Jacobs B., Objects and Classes, Co-Algebraically, [In:] Object Orientation with Prallelism and Persistence, Volume 370 of the series The Kluwer International Series in Engneering and Computer Science, Springer US, 1996, 83-103.
• [7] Jacobs B., Rutten J., A tutorial on (co)algebras and (co)induction, Bulletin of the European Association for Theoretical Computer Science 1997, 62, 222-259.
• [8] Slodičák V., Macko P., Some New Approaches in Functional Programming Using Algebras and Coalgebras, [In:] Electronic Notes in Theoretical Computer Science 2011, 279, 3, 41-62.
• [9] Ehrig H., Mahr B., Fundamentals of Algebraic Specification 1: Equations and Initial Semantics, EATCS Monographs on Theoretical Computer Science, 1985.
• [10] Jacobs B., Rutten J., An introduction to (co)algebras and (co)induction, [In:] D. Sangiorgi, J. Rutten (eds), Advanced Topics in bisimulation and coinduction, 2011, 38-99.
• [11] Chin W., A brief introduction to coalgebra representation theory, [In:] J. Bergen, S. Catoiu, W. Chin (eds.), Hopf Algebras, Marcel Dekker Inc., USA, 2004, 109-133.
• [12] Brandenburg M., Einführung in die Kategorientheorie, Springer Spektrum 2016.
• [13] Walters R.F.C., Categories and Computer Science, Cambridge University Press, New York 1992.
• [14] Awodey S., Category Theory, Carnegie Mellon University, 2005.
• [15] Escardó M.H., Streicher T., Induction and recursion on the partial real line with applications to real PCF, Theoretical Computer Science 1999, 210, 1, 121-157.
• [16] Goldblatt R., A calculus of terms for coalgebras of polynomial functors, Electr. Notes of Theroretical Computer Science 2001, 14, 1.
• [17] Kock J., Notes on polynomial endofunctors, Universitat Autonoma de Barcelona, 2007.
• [18] Deák A., Mihályi D., Jakab F., Exception modeling in the category, Proc. ICETA, IEEE, New York 2016, 49-53.
• [19] Crole R.L., Lectures on (co)induction and (co)algebras, Dept. Mathematics and Computer Science, University Leicester 2006.
• [20] Fernández M., Programming Languages and Operational Semantics: A Concise Overview, Springer, 2014.
• [21] Nygaard M., Transition Systems, University of Aarhus, 2004.
• [22] Ivaniga T., Ovseník Ľ., Turán J., Experimental Model of Passive Optical Network Technical University of Košice. ICCC 2015: 16th International Carpathian Control Conference, May 27-30, 2015, Szilvásvárad, Hungary, 186-189.
• [23] Steingartner W., Novitzká V., Categorical model of structural operational semantics of imperative language, J. Informational and Organizational Sciences 2016, 40, 2.
• [24] Plotkin G.D., The origins of structural operational semantics, J. of Logic and Algebraic Programming 2004, 60-61, 3-15.
• [25] Sculthorpe N., Torrini P., Mosses P.D., A modular structural operational semantics for delimited continuations, Proc. Workshop in Continuations, London 2015, 63-80.
• [26] Hughes J., A Study of Categories of Algebras and Coalgebras, Ph.D. Thesis, Carnegie Mellon University, Pittsburgh PA 2001.
• [27] Adámek J., Milius S., Moss L.S., Initial algebras and terminal coalgebras, 2010 (unpublished).
• [28] Herceg Đ., Radaković D., Extensibility of an Interpreted Language Using Plugin Libraries, Numerical Analysis and Applied Mathematics ICNAAM 2011, AIP Conf. Proc. 2011, 1389, 837-840.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).