Document - Interaction and observation: categorical semantics of reactive systems trough dialgebras

2013

Conference article Open Access

Interaction and observation: categorical semantics of reactive systems trough dialgebras

Ciancia V.

Computer Science - Formal Languages and Automata Theory D.3.1 Formal Definitions and Theory FOS: Computer and information sciences Semantics F.1.2 Modes of Computation Dialgebra Computer Science - Logic in Computer Science Formal Languages and Automata Theory (cs.FL) Interactive Systems Logic in Computer Science (cs.LO)

We use dialgebras, generalising both algebras and coalgebras, as a complement of the standard coalgebraic framework, aimed at describing the semantics of an interactive system by the means of reaction rules. In this model, interaction is built-in, and semantic equivalence arises from it, instead of being determined by a (possibly difficult) understanding of the side effects of a component in isolation. Behavioural equivalence in dialgebras is determined by how a given process interacts with the others, and the obtained observations. We develop a technique to inter-define categories of dialgebras of different functors, that in particular permits us to compare a standard coalgebraic semantics and its dialgebraic counterpart. We exemplify the framework using the CCS and the ?-calculus. Remarkably, the dialgebra giving semantics to the ?-calculus does not require the use of presheaf categories.

Source: CALCO 2013 - 5th Conference on Algebra and Coalgebra in Computer Science, pp. 110–125, Warsaw, Poland, 3-6 Settembre 2013

Publisher: SPRINGER-VERLAG BERLIN, HEIDELBERGER PLATZ 3, W-1000 BERLIN 33, GERMANY, Berlin, DEU

Citations

Hagino, T.: A Categorical Programming Language. PhD thesis, University of Edinburgh (1987)
Poll, E., Zwanenburg, J.: From algebras and coalgebras to dialgebras. Electronic Notes in Theoretical Computer Science 44(1) (2001) 289 - 307
Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theoretical Computer Science 249(1) (2000) 3 - 80
Voutsadakis, G.: Universal dialgebra: unifying algebra and coalgebra. Far East Journal of Mathematical Sciences 44(1) (2010) 1-53
Ciancia, V.: Interaction and observation, categorically. In: Proceedings Fourth Interaction and Concurrency Experience. Volume 59. (2011) 25-36
Leifer, J.J., Milner, R.: Deriving bisimulation congruences for reactive systems. In: In Proc. of CONCUR 2000, 2000. LNCS 1877, Springer (2000) 243-258
Sewell, P.: From rewrite rules to bisimulation congruences. Theor. Comput. Sci. 274 (March 2002) 183-230
Sassone, V., Sobocinski, P.: Deriving bisimulation congruences using 2-categories. Nord. J. Comput. 10(2) (2003) 163-
Turi, D., Plotkin, G.: Towards a mathematical operational semantics. In: 12th Annual IEEE Symposium on Logic in Computer Science (LICS), IEEE Computer Society (1997) 280-291
Milner, R.: A Calculus of Communicating Systems. Springer-Verlag New York, Inc. (1982)
Staton, S.: Relating coalgebraic notions of bisimulation: with applications to namepassing process calculi. In: 3rd international conference on Algebra and coalgebra in computer science, Springer-Verlag (2009) 191-205
Sangiorgi, D., Walker, D.: The Pi-Calculus - a theory of mobile processes. Cambridge University Press (2001)

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:271064,
	title = {Interaction and observation: categorical semantics of reactive systems trough dialgebras},
	author = {Ciancia V.},
	publisher = {SPRINGER-VERLAG BERLIN, HEIDELBERGER PLATZ 3, W-1000 BERLIN 33, GERMANY, Berlin, DEU},
	doi = {10.1007/978-3-642-40206-7_10 and 10.48550/arxiv.1209.5903},
	booktitle = {CALCO 2013 - 5th Conference on Algebra and Coalgebra in Computer Science, pp. 110–125, Warsaw, Poland, 3-6 Settembre 2013},
	year = {2013}
}