Bialgebras: Some Foundations for Distributed and Concurrent Computation¹

Article type: Research Article

Authors: Benson, David B.

Affiliations: Computer Science Department, Washington State University, Pullman, Washington, 99164-1210, U.S.A., csnet: [email protected]

Note: [1] Research supported in part by National Science Foundation grants DCR-8402305 and CCR-8801886.

Abstract: A categorical bimonoid consists of a monoid and a comonoid which act homomorphically on one another. In applications bimonoids are typically called bialgebras or Hopf algebras. The definitions are given at a level suitable to computer science applications and examples are included. The elements of the theory of graded bialgebras are developed and we provide a universal recursion theorem for morphisms between algebras and between coalgebras. With this theory we explicate refinements of concurrent programs and give a treatment of traces. The concluding section characterizes all coalgebras which interact with the match algebra to form a bialgebra and characterizes all algebras which interact with the fork (diagonal) coalgebra to form a bialgebra.

DOI: 10.3233/FI-1989-12402

Journal: Fundamenta Informaticae, vol. 12, no. 4, pp. 427-486, 1989