Hostname: page-component-7c8c6479df-r7xzm Total loading time: 0 Render date: 2024-03-29T00:21:44.393Z Has data issue: false hasContentIssue false

Pointwise extensions of GSOS-defined operations

Published online by Cambridge University Press:  25 March 2011

HELLE HVID HANSEN
Affiliation:
Technische Universiteit Eindhoven and Centrum Wiskunde & Informatica, P.O. Box 513, 5300 MB Eindhoven, The Netherlands Email: h.h.hansen@tue.nl
BARTEK KLIN
Affiliation:
University of Cambridge and University of Warsaw, 15 JJ Thomson Avenue, Cambridge CB3 0FD, U.K. Email: klin@mimuw.edu.pl

Abstract

Final coalgebras capture system behaviours such as streams, infinite trees and processes. Algebraic operations on a final coalgebra can be defined by distributive laws (of a syntax functor Σ over a behaviour functor F). Such distributive laws correspond to abstract specification formats. One such format is a generalisation of the GSOS rules known from structural operational semantics of processes. We show that given an abstract GSOS specification ρ that defines operations σ on a final F-coalgebra, we can systematically construct a GSOS specification ρ that defines the pointwise extension σ of σ on a final FA-coalgebra. The construction relies on the addition of a family of auxiliary ‘buffer’ operations to the syntax. These buffer operations depend only on A, so the construction is uniform for all σ and F.

Type
Paper
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aceto, L., Fokkink, W. J. and Verhoef, C. (2001) Structural operational semantics. In: Bergstra, J. A., Ponse, A. and Smolka, S. (eds.) Handbook of Process Algebra, Elsevier 197292.Google Scholar
Aczel, P. and Mendler, N. (1989) A final coalgebra theorem. In: Pitt, D., Rydeheard, D., Dybjer, P., Pitts, A. and Poigné, A. (eds.) Category Theory and Computer Science. Springer-Verlag Lecture Notes in Computer Science 389 357365.Google Scholar
Bartels, F. (2004) On Generalised Coinduction and Probabilistic Specification Formats, Ph.D. thesis, Vrije Universiteit Amsterdam.Google Scholar
Carton, O. (2000) Wreath product and infinite words. Journal of Pure and Applied Algebra 153 129150.Google Scholar
Hansen, H. and Klin, B. (2010) Pointwise extensions of GSOS-defined operations (extended abstract). In: CMCS 10 – Short Contributions. CWI Technical Report, SEN-1004, Centrum Wiskunde & Informatica, Amsterdam, The Netherlands 10–11.Google Scholar
Hansen, H. H. and Rutten, J. J. M. M. (2010) Symbolic synthesis of Mealy machines from arithmetic bitstream functions. Scientific Annals of Computer Science XX 97130.Google Scholar
Hehner, E. and Horspool, R. (1979) A new representation of the rational numbers for fast easy arithmetic. SIAM Journal on Computing 8 124134.Google Scholar
Jacobs, B. (2006) A bialgebraic review of deterministic automata, regular expressions and languages. In: Futatsugi, K., Jouannaud, J.-P. and Meseguer, J. (eds.) Algebra, Meaning and Computation: Essays dedicated to Joseph A. Goguen on the Occasion of his 65th Birthday. Springer-Verlag Lecture Notes in Computer Science 4060 375404.Google Scholar
Klin, B. (2009) Bialgebraic methods and modal logic in structural operational semantics. Information and Computation 207 237257.Google Scholar
Koblitz, N. (1984) P-adic numbers, p-adic Analysis, and Zeta-Functions, second edition, Graduate Texts in Mathematics, Springer-Verlag.Google Scholar
Lambek, J. (1968) A fixpoint theorem for complete categories. Mathematische Zeitschrift 103 (2)151161.Google Scholar
Lenisa, M., Power, J. and Watanabe, H. (2004) Category theory for operational semantics. Theoretical Computer Science 327 (1-2) 135154.Google Scholar
Pin, J.-E. and Weil, P. (2002) The wreath product principle for ordered semigroups. Communications in Algebra 30 56775713.Google Scholar
Rutten, J. (1991) Coalgebra, concurrency and control. CWI Research Report SEN-9921, Centrum Wiskunde & Informatica, Amsterdam, The NetherlandsGoogle Scholar
Rutten, J. (2000) Universal coalgebra: a theory of systems. Theoretical Computer Science 249 380.Google Scholar
Rutten, J. (2003) Behavioural differential equations: a coinductive calculus of streams, automata and power series. Theoretical Computer Science 308 (1)153.Google Scholar
Rutten, J. (2006) Algebraic specification and coalgebraic synthesis of Mealy machines. In: Proceedings of the 2nd International Workshop on Formal Aspects of Component Software (FACS 2005). Electronic Notes in Theoretical Computer Science 160 305319.Google Scholar
Rutten, J. and Turi, D. (1994) Initial algebra and final coalgebra semantics for concurrency. In: de Bakker, J., de Roever, W.-P. and Rozenberg, G. (eds.) A Decade of Concurrency, Reflections and Perspectives, REX School/Symposium. Springer-Verlag Lecture Notes in Computer Science 803 530582.Google Scholar
Straubing, H. (1989) The wreath product and its applications. In: Formal Properties of Finite Automata and Applications. Springer-Verlag Lecture Notes in Computer Science 386 1524.Google Scholar
Turi, D. and Plotkin, G. (1997) Towards a mathemathical operational semantics. In: Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science (LICS 1997), IEEE Computer Society 280291.Google Scholar
Worrell, J. (2005) On the final sequence of a finitary set functor. Theoretical Computer Science 338 184199.Google Scholar