5
$\begingroup$

I would like to know of some uses of algebraic structures to study computer science. Parallels of what I am looking for would be stuff like the fundamental group/homology/cohomology in topology and class fields in number theory where groups/rings are used to represent information about the object we are studying. I am not asking for examples like the graph isomorphism problem. Is there any equivalent in computer science? I would very much appreciate references too.

$\endgroup$
1

3 Answers 3

3
$\begingroup$

Look at Maurice Herlihy's work on applications of topology in distributed computing. He won a Turing award for it. :)

$\endgroup$
0
$\begingroup$

I'm not sure this is what you're interested in properly, but this book shows "applications" of abstract algebra, and a nice unusual example of finite semigroup (see this later answer), in the context of computing machines.

$\endgroup$
0
$\begingroup$

Abstract Algebra is commonly used to formalize the idea of combination and composition on a general level. There are many examples but I will discuss what I know here.

There are formalisms used to clarify what it means to combine types.

  • In the category of "types" in category theory, where morphisms are computable functions, one can use the notions of product and coproduct (or sum type) to define binary operations.
  • A semigroup is used to capture the idea of building types from others unrestrictedly since a semigroup has closure and associativity properties, a step better than category theory.
  • From a semigroup, if one adds and identity, you get a monoid; if you add inverses to a monoid, you get a group. A group can formalize composition of invertible functions. From this intuition, groups can represent systems of lossless compression algorithms.
  • Driving all categorial explorations in computer science is possibly the Curry-Howard correspondence.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .