Corradini A., Ferrari G. L., Montanari U. Transition systems with algebraic structure as models of computations. In: Semantics of Systems of Concurrent Processes LITP Spring School on Theoretical Computer Science. (La Roche Posay, France, 23 - 27 April 1990). Proceedings, vol. 469 pp. 185 - 222. I. Guessarian (ed.). (Lecture Notes in Computer Science, vol. Computer Science). Springer Berlin / Heidelberg, 1990. |

Abstract (English) |
Abstract. This paper is a tutorial introduction to a general methodology, consisting of categorical constructions, for the definition of new algebraic semantics for transition-based formalisms. The methodology individuates three leveIs of semantic description: programs, s~uctured transition systems, and models. The various formalisms differ for the structure on states and transitions, with respect to which all the categorical constructions of the methodology are paranaetric. These constructions generate i n an automatic way the induced transition system and the free model of a program. One characterizing issue of the methodology is that structured transition systems have a (usually algebraic) structure on both the states and the transitions, while for example in Plotkin's SOS approach just the structure of states is relevant. The advantage of considering transition systems with an algebraic structure on transitions, too, resides in the fact that often the same structure can be automatically extended to the computations of the system. This yields to categories whose arrows are not simple sequences of elementary transitions, but are instead abstract computations, equipped with a rich algebraic structure. The methodology generalizes the algebraic treatment of Petri nets proposed in [MM88], and includes the main ideas of the algebraic semantics for Horn Clause Logic presented in [Co90, CM90], and of the algebraic treatment of Milner's CCS, reported in [Fe90, FM90]. | |

URL: | http://www.springerlink.com/content/f745v6x274g5570p/ | |

DOI: | 10.1007/3-540-53479-2_8 | |

Subject |

1) Download Document PDF |

Open access Restricted Private