<p>My all-time favorite application of group theory in TCS is Barrington's Theorem. You can find <a href="http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html">an exposition of this theorem on the complexity blog</a>, and Barrington's exposition in the comment section of that post.</p>

CC BY-SA 3.0
2012-03-31T06:15:59.623Z
+1: and many consider it as one of the most surprising results in complexity theory. :)
Kaveh
CC BY-SA 3.0
2012-03-30T22:55:06.807Z
2012-03-30T22:55:06.807Z
Dai Le
<p>Universal algebra is an important tool in studying the complexity of constraint satisfaction problems. </p>

<p>For example, the <em>Dichotomy Conjecture</em> states that, roughly speaking, a constraint satisfaction problem over a finite domain is either NP-complete or polynomial-time solvable. Note that by Ladner's theorem there are problems in NP which are not in P and not NP-complete, unless P = NP, so the conjecture says that CSPs are special in having a dichotomy that the larger complexity classes do not have. It also would provide some explanation why most problems we encounter in practice can be classified to be either NP-complete or in P. </p>

<p>Dichotomies were proven for several special cases, e.g. binary domain CSPs (Schaefer) and ternary domain CSPs (Bulatov), and homomorphisms into undirected graphs (Hell and Nesetril). But the general case is fairly open. One of the major lines of attack is through universal algebra. Very roughly (and I am definitely not an expert in this!) one defines a polymorphism of CSP to be a function on the domain of the CSP which leaves all satisfied constraints satisfied if it is applied to each variable. The set of polymorphisms of a CSP in some sense captures its complexity. For example if a CSP A admits all polymorphisms of a CSP B, then A is polynomial time reducible to B. The set of polymorphisms forms an algebra, whose structure seems helpful in desining algorithms/showing reductions. For example if the polymorphism algebra of a CSP is idempotent and admits the unary type, then the CSP is NP-complete. Idempotence is a simplifying assumption that can be made more or less without loss of generality. Showing that a CSP whose algebra is idempotent and does not admit the unary type can be solved in polynomial time will prove the Dichotomy Conjecture.</p>

<p>See the survey by Bulatov: <a href="http://www.springerlink.com/content/a553847g6h673k05/">http://www.springerlink.com/content/a553847g6h673k05/</a>.</p>

CC BY-SA 3.0
2012-04-02T15:02:23.317Z
2012-04-02T15:02:23.317Z
Sasho Nikolov
<p>Lattices and fixed points are at the foundations of program analysis and verification. Though advanced results from lattice theory are rarely used because we are concerned with algorithmic issues such as computing and approximating fixed points, while research in lattice theory has a different focus (connections to topology, duality theory, etc). The initial abstract interpretation papers use basic lattice theory. The work of Roberto Giacobazzi and his collaborators uses more advanced results.</p>

<p>In distributed computing, a celebrated family of impossibility results was derived using methods of algebraic topology (See the work of Maurice Herlihy and Nir Shavit).</p>

<p>[Edit: See <a href="https://cstheory.stackexchange.com/questions/2898/applications-of-topology-to-computer-science">Applications of Topology to Computer Science</a>.]</p>

CC BY-SA 3.0
2012-04-02T01:55:50.807Z
2012-04-02T10:36:35.873Z
2017-04-13T12:32:28.053Z
Vijay D
<p>Rings, modules, and algebraic varieties are used in error correction and, more generally, coding theory.</p>

<p>Specifically, there is an abstract error correcting scheme (algebraic-geometry codes) which generalizes Reed-Solomon codes and Chinese Remainder codes. The scheme is basically to take your messages to come from a ring R and encode it by taking its residues modulo many different ideals in R. Under certain assumptions about R, one can prove that this makes a decent error correcting code.</p>

<p>In the world of list decoding, a recent <a href="http://arxiv.org/pdf/1106.0436.pdf">paper</a> by Guruswami gives an linear-algebraic method of list decoding folded Reed-Solomon codes, which has the nice property that all of the candidate messages lie in a low-dimensional affine subspace of the message space. One can construct <strong>subspace evasive sets</strong>, sets which are almost as large as the whole space but have small intersection with every low-dimensional affine subspace. If one restricts messages to come from a subspace evasive set inside the message space, then Guruswami's scheme gives an algorithm that guarantees nice list size. So far the only explicit construction of subspace evasive sets is given by Dvir and Lovett in their upcoming STOC paper, <a href="http://arxiv.org/pdf/1110.5696.pdf">Subspace Evasive Sets</a> and construct the set by taking a specific affine variety (and taking its Cartesian product with itself).</p>

CC BY-SA 3.0
2012-05-06T19:44:26.353Z
2012-05-06T19:44:26.353Z
Alan Guo
<p>Here are two applications from a different part of TCS.</p>

<p>Semirings are used for modelling annotations in databases (especially those needed for provenance), and often also for the valuation structures in valued constraint satisfaction.  In both of these applications, individual values must be combined together in ways which lead naturally to a semiring structure, with associativity and the one semiring operation distributing over the other.  Regarding your query about modules, neither monoid has an inverse in these applications, in general.</p>

<ul>
<li>Todd J. Green, Grigoris Karvounarakis and Val Tannen. <em>Provenance semirings</em>, PODS 2007.  <a href="http://dx.doi.org/10.1145/1265530.1265535">doi:10.1145/1265530.1265535</a> (<a href="http://www.ics.forth.gr/~gregkar/publications/pods2007.pdf">preprint</a>)</li>
<li>Stefano Bistarelli, Ugo Montanari and Francesca Rossi.  <em>Semiring-based constraint satisfaction and optimization</em>, JACM 1997.  <a href="http://dx.doi.org/10.1145/256303.256306">doi:10.1145/256303.256306</a> (<a href="http://www.math.unipd.it/~frossi/jacm.pdf">preprint</a>)</li>
</ul>

CC BY-SA 3.0
2012-03-31T16:06:03.023Z
2012-03-31T16:06:03.023Z
András Salamon
<p>Here is a very nice, practical use: <a href="http://www.cse.cuhk.edu.hk/~chi/papers/conn.pdf" rel="noreferrer">an algorithm for computing graph connectivity</a> (from <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6108166" rel="noreferrer">FOCS2011</a>). To compute the s->t connectivity of a graph, the authors give an algorithm that assigns random vectors with entries drawn from a finite field to the out edges from s, then construct similar vectors for all of the edges in the graph by taking random linear combinations, and finally discover the connectivity by computing the rank of the resulting vectors assigned to the in-edges of t. </p>

CC BY-SA 3.0
2012-03-31T16:17:55.863Z
Thanks for the pointer and overview!  This was from FOCS 2011: http://dx.doi.org/10.1109/FOCS.2011.55
András Salamon
CC BY-SA 3.0
2012-03-30T23:28:22.497Z
2013-02-24T21:46:29.180Z
2013-02-24T21:46:29.180Z
Aaron Roth
<p>Groups, rings, fields, and modules are everywhere in computational topology.  See especially Carlsson and Zomorodian's work [ex: <a href="http://www.cs.dartmouth.edu/~afra/papers/socg04/persistence.pdf">1</a>] on (multidimensional) persistent homology, which is all about graded modules over principal ideal domains.</p>

CC BY-SA 3.0
2012-03-31T09:43:20.783Z
@JeffE, links, please.
Nobody
CC BY-SA 3.0
2012-03-31T12:03:35.933Z
@JeffE, my comment was not meant to be offensive. Yes I do know how to Google. My point was, is there a particular article written by Carlsson and Zomorodian, which would be sort of overview of persistent homology? If there is one, please let us know. Thanks.
Nobody
CC BY-SA 3.0
2012-03-31T12:10:38.980Z
I suggest starting with [this paper](http://www.cs.dartmouth.edu/~afra/papers/socg04/persistence.pdf).  (Sorry, my earlier comment was uncalled for.)
Jeffε
CC BY-SA 3.0
2012-03-31T12:16:12.283Z
@JeffE, got it, exactly what I was looking for. Thanks.
Nobody
CC BY-SA 3.0
2012-03-31T09:36:54.710Z
2012-04-01T23:19:18.013Z
2012-04-01T23:19:18.013Z
Jeffε
<p>Algebra (and algebraic geometry) has had a pretty big role to play in cryptography, with elliptic curve groups, (number-theoretic) lattices, and of course $\mathbb{Z}_p$ being the basis for nearly all modern cryptographic work.</p>

CC BY-SA 3.0
2016-03-03T13:59:25.580Z
As I understand, there are other algebraic structures (finite fields, rings, and other structures) being used in modern Crypto -- which is gradually abandoning number theory and focusing more on lattices, error-correcting codes and "quantum-resistant" problems.
josh
CC BY-SA 3.0
2015-12-27T04:02:36.737Z
2015-12-27T04:02:36.737Z
Pratyush Mishra
<p>Analyzing any problem with a lot of symmetry is facilitated by using group theory. An example would be to find algorithms for things like rubic's cube. Although I do not know the details, I am sure that proving that <a href="http://www.cube20.org/" rel="noreferrer">God's number is 20</a> required some serious group theoretical pruning. In a different context, practical solvers for graph isomorphism problem like <a href="http://cs.anu.edu.au/~bdm/nauty/" rel="noreferrer">nauty</a> use the automorphism group of the graph.</p>

CC BY-SA 3.0
2012-05-08T16:52:12.490Z
Also, the algorithms for graph isomorphism [Luks '81; Babai--Luks '82] with the best-known guarantees (that is, works in theory, but may be inefficient in practice) use group theory heavily, even invoking the classification of finite simple groups.
Joshua Grochow
CC BY-SA 3.0
2012-03-30T21:31:02.933Z
2012-03-30T21:31:02.933Z
Shitikanth
<p>Check out <em>Ramsey Theory</em> -- basically a significant generalization of the <em>pigeonhole principle</em> which underlies a lot of automata and formal language theory (or should I say, the pigeonhole principle is the simplest case of Ramsey Theory). It basically says that even highly disordered structures turn out to necessarily contain a lot of order if they are sufficiently large. For a small example just beyond the pigeonhole principle, note that if you take any six people, then either three of them mutually know each other or three of them mutually do not know each other.</p>

<p><a href="http://www.cs.yale.edu/clique/resources/ramsey.pdf" rel="noreferrer">This paper</a> looks like a nice place to start for connections with computer science, but you can google for more. It's more combinatoric than algebraic in its basic nature, but has many applications in algebra and theoretical CS.</p>

<p>And also check out the story of the inventor, <a href="http://en.wikipedia.org/wiki/Frank_P._Ramsey" rel="noreferrer">Frank Ramsey</a> -- truly a remarkable polymath who made fundamental, even revolutionary contributions in economics and philosophy as well as mathematics, many unappreciated until much later, all before dying at the age of 26 -- just think! In fact, Ramsey's original theorem, the basis of Ramsey Theory, was a mere lemma in a paper with a bigger aim in mathematical logic.</p>

CC BY-SA 3.0
2012-04-03T03:59:56.630Z
this is classical extremal combinatorics stuff, i am wondering where do you see the connection with algebra? (i don't debate that ramsey theory is a source of great problems and theorems)
Sasho Nikolov
CC BY-SA 3.0
2012-04-03T11:14:20.160Z
Well, for one, graph theory is extremely important in theoretical CS.  And check out the link in my answer as well as [this search](https://www.google.com/search?q=ramsey+theory+computer&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a).  Also, from Pin, J.E., _Varieties of formal languages_, Theorem 1.11 -- Any finite semigroup $S$ generated by $A$, $k >= 2$ has $n$ with every word $w \in A^+$ loinger than $n$ having idempotent $e \in S$ with $w = xu_1...u_ny$, $x, y \in A^*$ and all $\bar u_i= e$. This is most easily proved with Ramsey's Theorem.
David Lewis
CC BY-SA 3.0
2012-04-03T14:07:40.193Z
i am not disputing the relevance of ramsey theory, let alone graph theory, to tcs. i am saying that the OP asked about applications of algebra and ramsey theory is not something  usually associated with algebra, afaik. but since you seem to have some connection ramsey theory -> algebra -> tcs in mind, maybe you can add that to your answer
Sasho Nikolov
CC BY-SA 3.0
2012-04-03T18:54:43.660Z
@Sasho -- If you mean that Ramsey Theory is not a topic of algebra, so my answer is off-base, then you are 100% correct. I apologize for my answer. I guess my mind tends to cross disciplinary and sub-disciplinary boundaries rather readily.  But it's worse than that -- Ramsey Theory is in no way an "algebraic structure". Please feel free to downvote my answer.  Regards.
David Lewis
CC BY-SA 3.0
2012-04-03T20:06:35.957Z
well while maybe downvoting would be logical, i love extremal combinatorics, so i am not going to :) BTW i am quite sure that there are some ramsey-type phenomena that occur with algebraic structures, maybe even at lower "densities" because of the symmetries, so you're giving me an idea about a question
Sasho Nikolov
CC BY-SA 3.0
2012-03-30T23:57:31.593Z
2012-03-31T00:08:50.773Z
2012-03-31T00:08:50.773Z
David Lewis
<p>Recently, we explore (see our paper on springerlink: <a href="https://link.springer.com/article/10.1007/s10115-017-1048-y" rel="nofollow noreferrer">A formal series-based unification of the frequent itemset mining approaches</a>) a unification attempt to pattern mining (a popular instance of data mining) approaches by mean of formal series and weighted automata. These tools are based on mappings between monoids and semiring structures. </p>

CC BY-SA 4.0
2019-03-18T21:34:02.693Z
2019-03-18T21:34:02.693Z
Slimane Oulad-Naoui
<p>In functional programming, the most general and elegant abstractions for problems are often algebraic (or category-theoretic) in nature: monoids, <a href="http://stedolan.net/research/semirings.pdf" rel="nofollow noreferrer">semirings</a>, functors, monads, F-algebras, F-coalgebras, etc. Some classic results (e.g., the Yoneda lemma) happen to have computational content and utility.</p>

<p>Also, there is homotopy type theory, which interprets type theory in (sort-of) an algebraic topological setting.</p>

CC BY-SA 4.0
2019-03-19T22:40:32.487Z
2019-03-19T22:40:32.487Z
xrq
<p>Most answers on this page are research-oriented. They answer the question: what algebraic structures will help us publish more theoretical papers on computer science. But most of those theoretical papers will not be directly relevant to the work of a software practitioner, even when the programs are written in Haskell or another functional language.</p>
<p>Most frequently, category theory is mentioned as the algebraic structure used in functional programming, so let me comment on that. Category theory has certain but limited use for learning functional programming or in actual practice of functional programming. I recently made a presentation to answer that question. <a href="https://www.youtube.com/watch?v=Zau8CxsfxOo" rel="nofollow noreferrer">https://www.youtube.com/watch?v=Zau8CxsfxOo</a></p>
<p>Summary:</p>
<ul>
<li>Functional programmers do not require category theory in order to master the main features and design patterns that FP uses to write better code. For example, one can (and should) first learn how to use monads, functors, liftings, map/filter/fold, etc., in a concrete programming language with specific examples. Category theory will not help master these techniques even though the words &quot;functor&quot; and &quot;monad&quot; originally come from category theory.</li>
<li>At a certain point, programmers will encouter examples of typeclasses with laws, and understand why those laws are important in practice.</li>
<li>There will be lots of laws. To make some order and system among those laws, we can formulate the laws as a generalized &quot;lifting&quot; type signature with &quot;twisted&quot; function types.</li>
<li>We can then use the definitions of category and functor as generalizations that cover the laws of functors, contrafunctors, filterable functors, filterable contrafunctors, monads, applicative functors, applicative contrafunctors, comonads, and perhaps other type classes.</li>
<li>I show some examples of categories that are used to describe functors, monads, applicatives, and filterable functors.</li>
<li>I cover filterable functors in more detail, with backdrop of category theory, because filterable functors are rarely explained as a separate typeclass.</li>
<li>Another example where category theory is useful: &quot;type constructor libraries&quot;, i.e. libraries with functions parameterized by a <em>type constructor</em>. Examples of these are free functor / free monad / etc., and Church encoding of types (including recursive type constructors, e.g. the Church encoding of a free monad). Programmers who need to implement these libraries will need to understand how these constructions are defined and what laws need to hold. Category theory provides some limited guidance about that.</li>
<li>Conclusion 1: programmers need to learn functional programming and not category theory. The special knowledge required in functional programming (e.g., how to implement and use a free applicative functor in your programming language) is not going to be covered by any book in category theory.</li>
<li>Conclusion 2: basic definitions of category theory (category, functor, natural transformation) are useful as condensed formulations of general laws for a number of typeclasses. Unless a programmer has experience dealing with all the different laws of those typeclasses, it is unlikely that an appreciation of category theory will be of much help. Even for programmers working with high-level type constructor libraries, a study of category theory is unlikely to be of any use beyond a few basic concepts and definitions (category, functor, natural transformation, monoid, initial object, Yoneda identities, F-algebra).</li>
<li>Conclusion 3: knowledge of category theory will not help us derive or prove laws for specific typeclasses, and will not help us implement those typeclasses correctly in code. The reason is that category theory is so general that it only talks about laws that apply generally to a large number of very different typeclasses (functor, monad, filterable functor, applicative functor, pointed functor, contravariant functor, etc.). For practical coding, e.g. to verify that our implementation of a specific monad is lawful, we need to learn not category theory but the techniques of symbolic derivation and proof.</li>
</ul>
<p>I am writing a new free textbook (&quot;Science of Functional Programming&quot;, <a href="https://github.com/winitzki/sofp" rel="nofollow noreferrer">https://github.com/winitzki/sofp</a>) to develop and explain these techniques with practical programmers in mind. My book is going to be very light on category theory, and I'm not going to use any advanced abstract concepts unless there is a significant gain for practical work. Having written down several hundred step-by-step proofs, I have found what derivation techniques are useful and what definitions from category theory are helpful when proving the theoretical properties of practically relevant code.</p>
<p>Examples of category theory knowledge that has, so far, proved to be unnecessary and <strong>not useful</strong>:</p>
<ul>
<li>monad is a monoid in the category of endofunctors</li>
<li>any monad comes from a pair of adjoint functors</li>
<li>a free monad comes from the free/forgetful functor adjunction</li>
</ul>
<p>In contrast, naturality laws are used in about 30% of all proofs, and the functor composition law is also used in around 30% of proofs. This shows the importance of learning the concepts of functor and natural transformation.</p>

CC BY-SA 4.0
2023-02-22T13:42:29.187Z
2023-02-23T09:02:27.453Z
2023-02-23T09:02:27.453Z
winitzki
<p>My impression is that, by and large, traditional algebra is rather too specific for use in Computer Science.  So Computer Scientists either use weaker (and, hence, more general) structures, or generalize the traditional structures so that they can fit them to their needs.  We also use category theory <em>a lot</em>, which mathematicians don't think of as being part of algebra, but we don't see why not.  We find the regimentation of traditional mathematics into "algebra" and "topology" as separate branches inconvenient, even pointless, because algebra is generally first-order whereas topology has a chance of dealing with higher-order aspects.  So, the structures used in Computer Science have algebra and topology mixed in.  In fact, I would say they tend more towards topology than algebra.  Regimentation of reasoning into "algebra" and "logic" is another pointless division from our point of view, because algebra deals with equational properties whereas logic deals with all other kinds of properties as well.</p>

<p>Coming back to your question, semigroups and monoids are used quite intensely in automata theory.  Eilenberg has written a <a href="http://books.google.co.uk/books?id=YkuXEJ34xF0C&amp;source=gbs_slider_cls_metadata_7_mylibrary&amp;redir_esc=y">2-volume collection</a>, the second of which is almost entirely algebra.  I am told that he was planning four volumes but his age did not allow the project to be finished.  Jean-Eric Pin has a modernized version of a lot of this content in an <a href="http://www.liafa.univ-paris-diderot.fr/~jep/PDF/MPRI/MPRI.pdf">online book</a>.  Automata are "monoid modules" (also called monoid actions or "acts"), which are at the right level of generality for Computer Science.  Traditional ring modules are probably too specific.</p>

<p>Lattice theory was a major force in the development of denotational semantics.  Topology was mixed into lattice theory when Computer Scientists, jointly with mathematicians, developed <a href="http://books.google.co.uk/books?id=2QLvAAAAMAAJ&amp;source=gbs_slider_cls_metadata_9_mylibrary">continuous lattices</a> and then generalized them to <a href="http://books.google.co.uk/books?id=xPF9Hb7DPLgC&amp;dq=continuous%20lattices&amp;source=gbs_similarbooks">domains</a>.  I would say that domain theory is Computer Scientists' own mathematics, which traditional mathematics has no knowledge of.</p>

<p>Universal algebra is used for defining <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.8285&amp;rep=rep1&amp;type=pdf">algebraic specifications of data types</a>.  Having gotten there, Computer Scientists immediately found the need to deal with more general properties: conditional equations (also called equational Horn clauses) and first-order logic properties, still using the same ideas of universal algebra.  As you would note, algebra now merges into model theory.</p>

<p>Category theory is the foundation for type theory.  As Computer Scientists keep inventing new structures to deal with various computational phenomena, category theory is a very comforting framework in which to place all these ideas.  We also use structures that are enabled by category theory, which don't have existence in "traditional" mathematics, such as functor categories.  Also, algebra comes back into the picture from a categorical point of view in the use of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.5275&amp;rep=rep1&amp;type=pdf">monads</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.5940&amp;rep=rep1&amp;type=pdf">algebraic theories of effects</a>.  <a href="http://ziman.functor.sk/files/coalgebras_and_coinduction.pdf">Coalgebras</a>, which are the duals of algebras, also find a lot of application.</p>

<p>So, there is a wide-ranging application of "algebra" in Computer Science, but it is not the kind of algebra found in traditional algebra textbooks.</p>

<p><strong>Additional note</strong>: There is a concrete sense in which category theory is algebra.  <em>Monoid</em> is a fundamental structure in algebra.  It consists of a binary "multiplication" operator that is associative and has an identity.  Category theory generalizes this by associating "types" to the elements of the monoid, $a : X \rightarrow Y$.  You can "multiply" the elements only when the types match: if $a : X \rightarrow Y$ and $b : Y \to Z$ then $ab : X \to Z$.  For example, $n \times n$ matrices have a multiplication operation making them a monoid.  However, $m \times n$ matrices (where $m$ and $n$ could be different) form a category.  Monoids are thus special cases of categories that have a single type.  Rings are special cases of additive categories that have a single type.  Modules are special cases of functors where the source and target categories have a single type.  So on.  Category theory is <em>typed algebra</em> whose types make it infinitely more applicable than traditional algebra.</p>

CC BY-SA 3.0
2012-03-31T11:38:37.663Z
Category theorists think of algebra as part of category theory.  Algebraists think of category theory as part of algebra.  Logicians think they're both crazy.
Jeffε
CC BY-SA 3.0
2012-03-31T16:06:56.610Z
there is plenty of interaction between topology and algebra in pure math...
Sasho Nikolov
CC BY-SA 3.0
2012-04-01T17:38:27.890Z
I should admit that the view I have of mathematics is mostly gleaned from graduate/undergraduate text books.  The researchers that work in the relevant areas might in fact have a more integrated view.  But, still, my experience is that there is much more of a silo culture in Mathematics than I find in Computer Science.
Uday Reddy
CC BY-SA 3.0
2012-04-01T20:44:14.007Z
It also occurs to me, since I wrote the above response, that the theory of imperative programming can possibly benefit a lot more than it has from semigroup theory.  We are at fault for not looking at it closely.  But I am trying to make [amends](http://www.disi.unige.it/person/ZuccaE/FOOL2011/paper6.pdf).
Uday Reddy
CC BY-SA 3.0
2012-04-02T21:48:23.943Z
This is a good answer, but I think that your comments about "regimentation" and "silo culture" are misleading.  The reason that algebra, topology, and logic seem unified to you is that *for the questions you care about*, the parts of these subjects that are relevant to you are very closely intertwined.  But if, for example, you were to try to classify 4-dimensional manifolds over the complex numbers, you would quickly see the usefulness of the traditional distinctions that mathematicians make.  It all depends on what problem you are trying to solve.
Timothy Chow
CC BY-SA 3.0
2012-04-04T10:55:37.420Z
@TimothyChow: No, I do not believe that the issues I raise have anything to do with the questions that I care about.  They are rather about the structure of mathematics itself.  I think a good response to my criticism would be to show us work that demonstrates how the different areas of mathematics fit together.
Uday Reddy
CC BY-SA 3.0
2012-04-06T14:16:33.160Z
@uday -- See the thread I started in Elienberg [here](http://cstheory.stackexchange.com/questions/10308/eilenbergs-rational-hiererchy-of-nonrational-automata-languages-where-is-i) and other places.  I think I have a clear idea where his ideas stand now -- the rational material has been developed rather nicely by Pin and others.  As for the super-rational, fragments have been reconstructed, but in the absence of his genius, there is nothing coherent and complete. I would be grateful for any information on what happened to Eilenberg personally that ended his work with some apparent suddenness.
David Lewis
CC BY-SA 3.0
2012-04-06T15:40:06.763Z
I am personally still entirely perplexed by pretty much any single inference you make about research culture in math and computer science. As @TimothyChow points out, different subfields were developed to deal with different kinds of problems, and therefore different tools were developed. Where it makes sense to bring tools from different subfields, and people have realized that, there is interaction. Examples should not be hard to find, for example in any lecture notes on lie algebra.
Sasho Nikolov
CC BY-SA 3.0
2012-04-06T15:46:02.623Z
with regards to there being less of a silo culture in computer science, i'd disagree there too. I personally have no idea why PL researchers need all this heavy machinery, what they use it for, what problem they solve with it, and why should I care. Maybe it's my own ignorance, but I doubt most complexity theorists and algorithmicists know the answers to these questions...
Sasho Nikolov
CC BY-SA 3.0
2012-04-06T19:46:04.337Z
@DavidLewis.  Sorry I don't know any more than you do about Eilenberg.  He is a lot better known for his category theory (understandably, because he is one of its founders), but the fact that he worked on automata theory was completely unknown to me until I ran into his book one day while browsing through the automata theory shelf in library.
Uday Reddy
CC BY-SA 3.0
2012-04-06T19:59:58.247Z
@SashoNikolov. If you don't know what all this theory is for, why don't you ask a question?  That is what this forum is for!
Uday Reddy
CC BY-SA 3.0
2012-04-06T20:12:32.833Z
I want to, but somehow "what does this  whole branch of CS do and why?" seems too open ended..or you think it's fine? but my point was, I think CS fields are even more segregated than math fields since we sometimes don't even share basic philosophies, even if you just take the theoretically minded ones.
Sasho Nikolov
CC BY-SA 3.0
2012-04-06T20:44:33.010Z
@SashoNikolov.  Well, speaking for myself, I work in programming theory.  The neighbouring disciplines for me are compilers, databases, operating systems, distributed systems and software engineering.  If you asked me, I would have something sensible to say about each of those things, where the boundaries are, how the emphasis might differ, where the interactions are, and where we borrow ideas from each other.  Similarly, I am expecting algebraists to be able to say similar things about their neighbouring areas: analysis and topology on one side and logic and model theory on the other.
Uday Reddy
CC BY-SA 3.0
2012-04-08T10:23:18.073Z
@SashoNikolov. "What does this whole branch of CS do and why?"  Why isn't that a reasonable question, especially since, as you say, some 70-80% of the people on this forum don't know the answer?  It would be a "big picture" question perhaps.
Uday Reddy
CC BY-SA 3.0
2012-03-31T09:43:23.810Z
2014-12-10T20:28:16.667Z
2014-12-10T20:28:16.667Z
Uday Reddy
<p>I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (and to a lesser degree, other sub-fields of computer science).</p>

<p>Under group theory I've come across syntactic monoids for formal languages and trace and history monoids for parallel/concurrent computing.</p>

<p>From a ring theory standpoint, I've come across semiring frameworks for graph processing and semiring based parsing.</p>

<p>I have yet to find any uses of algebraic structures from module theory in my research (and would like to).</p>

<p>I'm assuming that there are further examples and that I'm just not looking in the right place to find them. </p>

<p>What are some other examples of algebraic structures from the domains listed above that are commonly found in theoretical computer science (and other sub-fields of computer science)? Alternatively, what journals or other resources can you recommend that might cover these topics?</p>

CC BY-SA 3.0
2012-03-30T21:02:41.310Z
This seems rather vast. All kinds of algebraic structures (groups, rings, semirings, semigroups, fields) show up in theoretical computer science, and it's pervasive enough that you'd be hard pressed to find a specific subcomponent. Also, don't forget finite fields for hashing and many other randomized fingerprinting methods.
Suresh Venkat
CC BY-SA 3.0
2012-03-30T21:36:27.900Z
Possibly anything that can be representable has an use in Computer Science!
v s
CC BY-SA 3.0
2012-09-25T21:13:11.883Z
see also [Applications of representation theory of the symmetric group](http://cstheory.stackexchange.com/questions/12691/applications-of-representation-theory-of-the-symmetric-group)
vzn
<reference-request><big-picture><big-list><algebra><survey>
Uses of algebraic structures in theoretical computer science
GEL
# Uses of algebraic structures in theoretical computer science

(Asked by: username_0 on 2012-03-30)

I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (and to a lesser degree, other sub-fields of computer science).

Under group theory I've come across syntactic monoids for formal languages and trace and history monoids for parallel/concurrent computing.

From a ring theory standpoint, I've come across semiring frameworks for graph processing and semiring based parsing.

I have yet to find any uses of algebraic structures from module theory in my research (and would like to).

I'm assuming that there are further examples and that I'm just not looking in the right place to find them.

What are some other examples of algebraic structures from the domains listed above that are commonly found in theoretical computer science (and other sub-fields of computer science)? Alternatively, what journals or other resources can you recommend that might cover these topics?

**Tags:** reference-request, big-picture, big-list, algebra, survey
> **Comments:**
> **username_1**: This seems rather vast. All kinds of algebraic structures (groups, rings, semirings, semigroups, fields) show up in theoretical computer science, and it's pervasive enough that you'd be hard pressed to find a specific subcomponent. Also, don't forget finite fields for hashing and many other randomized fingerprinting methods.  
> **username_2**: Possibly anything that can be representable has an use in Computer Science!  
> **username_3**: see also [Applications of representation theory of the symmetric group](http://cstheory.stackexchange.com/questions/12691/applications-of-representation-theory-of-the-symmetric-group)  

---

## 14 answers

### Answer by username_21 on 2012-03-31. Score: 56 | Accepted answer

My impression is that, by and large, traditional algebra is rather too specific for use in Computer Science. So Computer Scientists either use weaker (and, hence, more general) structures, or generalize the traditional structures so that they can fit them to their needs. We also use category theory *a lot*, which mathematicians don't think of as being part of algebra, but we don't see why not. We find the regimentation of traditional mathematics into "algebra" and "topology" as separate branches inconvenient, even pointless, because algebra is generally first-order whereas topology has a chance of dealing with higher-order aspects. So, the structures used in Computer Science have algebra and topology mixed in. In fact, I would say they tend more towards topology than algebra. Regimentation of reasoning into "algebra" and "logic" is another pointless division from our point of view, because algebra deals with equational properties whereas logic deals with all other kinds of properties as well.

Coming back to your question, semigroups and monoids are used quite intensely in automata theory. Eilenberg has written a [2-volume collection](http://books.google.co.uk/books?id=YkuXEJ34xF0C&source=gbs_slider_cls_metadata_7_mylibrary&redir_esc=y), the second of which is almost entirely algebra. I am told that he was planning four volumes but his age did not allow the project to be finished. Jean-Eric Pin has a modernized version of a lot of this content in an [online book](http://www.liafa.univ-paris-diderot.fr/~jep/PDF/MPRI/MPRI.pdf). Automata are "monoid modules" (also called monoid actions or "acts"), which are at the right level of generality for Computer Science. Traditional ring modules are probably too specific.

Lattice theory was a major force in the development of denotational semantics. Topology was mixed into lattice theory when Computer Scientists, jointly with mathematicians, developed [continuous lattices](http://books.google.co.uk/books?id=2QLvAAAAMAAJ&source=gbs_slider_cls_metadata_9_mylibrary) and then generalized them to [domains](http://books.google.co.uk/books?id=xPF9Hb7DPLgC&dq=continuous%20lattices&source=gbs_similarbooks). I would say that domain theory is Computer Scientists' own mathematics, which traditional mathematics has no knowledge of.

Universal algebra is used for defining [algebraic specifications of data types](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.8285&rep=rep1&type=pdf). Having gotten there, Computer Scientists immediately found the need to deal with more general properties: conditional equations (also called equational Horn clauses) and first-order logic properties, still using the same ideas of universal algebra. As you would note, algebra now merges into model theory.

Category theory is the foundation for type theory. As Computer Scientists keep inventing new structures to deal with various computational phenomena, category theory is a very comforting framework in which to place all these ideas. We also use structures that are enabled by category theory, which don't have existence in "traditional" mathematics, such as functor categories. Also, algebra comes back into the picture from a categorical point of view in the use of [monads](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.5275&rep=rep1&type=pdf) and [algebraic theories of effects](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.5940&rep=rep1&type=pdf). [Coalgebras](http://ziman.functor.sk/files/coalgebras_and_coinduction.pdf), which are the duals of algebras, also find a lot of application.

So, there is a wide-ranging application of "algebra" in Computer Science, but it is not the kind of algebra found in traditional algebra textbooks.

**Additional note**: There is a concrete sense in which category theory is algebra. *Monoid* is a fundamental structure in algebra. It consists of a binary "multiplication" operator that is associative and has an identity. Category theory generalizes this by associating "types" to the elements of the monoid, $a : X \rightarrow Y$. You can "multiply" the elements only when the types match: if $a : X \rightarrow Y$ and $b : Y \to Z$ then $ab : X \to Z$. For example, $n \times n$ matrices have a multiplication operation making them a monoid. However, $m \times n$ matrices (where $m$ and $n$ could be different) form a category. Monoids are thus special cases of categories that have a single type. Rings are special cases of additive categories that have a single type. Modules are special cases of functors where the source and target categories have a single type. So on. Category theory is *typed algebra* whose types make it infinitely more applicable than traditional algebra.

> **Comments:**
> **username_11**: Category theorists think of algebra as part of category theory.  Algebraists think of category theory as part of algebra.  Logicians think they're both crazy.  
> **username_6**: there is plenty of interaction between topology and algebra in pure math...  
> **username_21**: I should admit that the view I have of mathematics is mostly gleaned from graduate/undergraduate text books.  The researchers that work in the relevant areas might in fact have a more integrated view.  But, still, my experience is that there is much more of a silo culture in Mathematics than I find in Computer Science.  
> **username_21**: It also occurs to me, since I wrote the above response, that the theory of imperative programming can possibly benefit a lot more than it has from semigroup theory.  We are at fault for not looking at it closely.  But I am trying to make [amends](http://www.disi.unige.it/person/ZuccaE/FOOL2011/paper6.pdf).  
> **username_22**: This is a good answer, but I think that your comments about "regimentation" and "silo culture" are misleading.  The reason that algebra, topology, and logic seem unified to you is that *for the questions you care about*, the parts of these subjects that are relevant to you are very closely intertwined.  But if, for example, you were to try to classify 4-dimensional manifolds over the complex numbers, you would quickly see the usefulness of the traditional distinctions that mathematicians make.  It all depends on what problem you are trying to solve.  
> **username_21**: @TimothyChow: No, I do not believe that the issues I raise have anything to do with the questions that I care about.  They are rather about the structure of mathematics itself.  I think a good response to my criticism would be to show us work that demonstrates how the different areas of mathematics fit together.  
> **username_17**: @uday -- See the thread I started in Elienberg [here](http://cstheory.stackexchange.com/questions/10308/eilenbergs-rational-hiererchy-of-nonrational-automata-languages-where-is-i) and other places.  I think I have a clear idea where his ideas stand now -- the rational material has been developed rather nicely by Pin and others.  As for the super-rational, fragments have been reconstructed, but in the absence of his genius, there is nothing coherent and complete. I would be grateful for any information on what happened to Eilenberg personally that ended his work with some apparent suddenness.  
> **username_6**: I am personally still entirely perplexed by pretty much any single inference you make about research culture in math and computer science. As @TimothyChow points out, different subfields were developed to deal with different kinds of problems, and therefore different tools were developed. Where it makes sense to bring tools from different subfields, and people have realized that, there is interaction. Examples should not be hard to find, for example in any lecture notes on lie algebra.  
> **username_6**: with regards to there being less of a silo culture in computer science, i'd disagree there too. I personally have no idea why PL researchers need all this heavy machinery, what they use it for, what problem they solve with it, and why should I care. Maybe it's my own ignorance, but I doubt most complexity theorists and algorithmicists know the answers to these questions...  
> **username_21**: @DavidLewis.  Sorry I don't know any more than you do about Eilenberg.  He is a lot better known for his category theory (understandably, because he is one of its founders), but the fact that he worked on automata theory was completely unknown to me until I ran into his book one day while browsing through the automata theory shelf in library.  
> **username_21**: @SashoNikolov. If you don't know what all this theory is for, why don't you ask a question?  That is what this forum is for!  
> **username_6**: I want to, but somehow "what does this  whole branch of CS do and why?" seems too open ended..or you think it's fine? but my point was, I think CS fields are even more segregated than math fields since we sometimes don't even share basic philosophies, even if you just take the theoretically minded ones.  
> **username_21**: @SashoNikolov.  Well, speaking for myself, I work in programming theory.  The neighbouring disciplines for me are compilers, databases, operating systems, distributed systems and software engineering.  If you asked me, I would have something sensible to say about each of those things, where the boundaries are, how the emphasis might differ, where the interactions are, and where we borrow ideas from each other.  Similarly, I am expecting algebraists to be able to say similar things about their neighbouring areas: analysis and topology on one side and logic and model theory on the other.  
> **username_21**: @SashoNikolov. "What does this whole branch of CS do and why?"  Why isn't that a reasonable question, especially since, as you say, some 70-80% of the people on this forum don't know the answer?  It would be a "big picture" question perhaps.  

---

### Answer by username_4 on 2012-03-30. Score: 29

My all-time favorite application of group theory in TCS is Barrington's Theorem. You can find [an exposition of this theorem on the complexity blog](http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html), and Barrington's exposition in the comment section of that post.

> **Comments:**
> **username_5**: +1: and many consider it as one of the most surprising results in complexity theory. :)  

---

### Answer by username_10 on 2012-03-30. Score: 15

Here is a very nice, practical use: [an algorithm for computing graph connectivity](http://www.cse.cuhk.edu.hk/~chi/papers/conn.pdf) (from [FOCS2011](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6108166)). To compute the s->t connectivity of a graph, the authors give an algorithm that assigns random vectors with entries drawn from a finite field to the out edges from s, then construct similar vectors for all of the edges in the graph by taking random linear combinations, and finally discover the connectivity by computing the rank of the resulting vectors assigned to the in-edges of t.

> **Comments:**
> **username_9**: Thanks for the pointer and overview!  This was from FOCS 2011: http://dx.doi.org/10.1109/FOCS.2011.55  

---

### Answer by username_11 on 2012-03-31. Score: 15

Groups, rings, fields, and modules are everywhere in computational topology. See especially Carlsson and Zomorodian's work [ex: [1](http://www.cs.dartmouth.edu/~afra/papers/socg04/persistence.pdf)] on (multidimensional) persistent homology, which is all about graded modules over principal ideal domains.

> **Comments:**
> **username_12**: @JeffE, links, please.  
> **username_12**: @JeffE, my comment was not meant to be offensive. Yes I do know how to Google. My point was, is there a particular article written by Carlsson and Zomorodian, which would be sort of overview of persistent homology? If there is one, please let us know. Thanks.  
> **username_11**: I suggest starting with [this paper](http://www.cs.dartmouth.edu/~afra/papers/socg04/persistence.pdf).  (Sorry, my earlier comment was uncalled for.)  
> **username_12**: @JeffE, got it, exactly what I was looking for. Thanks.  

---

### Answer by username_6 on 2012-04-02. Score: 14

Universal algebra is an important tool in studying the complexity of constraint satisfaction problems.

For example, the *Dichotomy Conjecture* states that, roughly speaking, a constraint satisfaction problem over a finite domain is either NP-complete or polynomial-time solvable. Note that by Ladner's theorem there are problems in NP which are not in P and not NP-complete, unless P = NP, so the conjecture says that CSPs are special in having a dichotomy that the larger complexity classes do not have. It also would provide some explanation why most problems we encounter in practice can be classified to be either NP-complete or in P.

Dichotomies were proven for several special cases, e.g. binary domain CSPs (Schaefer) and ternary domain CSPs (Bulatov), and homomorphisms into undirected graphs (Hell and Nesetril). But the general case is fairly open. One of the major lines of attack is through universal algebra. Very roughly (and I am definitely not an expert in this!) one defines a polymorphism of CSP to be a function on the domain of the CSP which leaves all satisfied constraints satisfied if it is applied to each variable. The set of polymorphisms of a CSP in some sense captures its complexity. For example if a CSP A admits all polymorphisms of a CSP B, then A is polynomial time reducible to B. The set of polymorphisms forms an algebra, whose structure seems helpful in desining algorithms/showing reductions. For example if the polymorphism algebra of a CSP is idempotent and admits the unary type, then the CSP is NP-complete. Idempotence is a simplifying assumption that can be made more or less without loss of generality. Showing that a CSP whose algebra is idempotent and does not admit the unary type can be solved in polynomial time will prove the Dichotomy Conjecture.

See the survey by Bulatov: <http://www.springerlink.com/content/a553847g6h673k05/>.


---

### Answer by username_7 on 2012-04-02. Score: 13

Lattices and fixed points are at the foundations of program analysis and verification. Though advanced results from lattice theory are rarely used because we are concerned with algorithmic issues such as computing and approximating fixed points, while research in lattice theory has a different focus (connections to topology, duality theory, etc). The initial abstract interpretation papers use basic lattice theory. The work of Roberto Giacobazzi and his collaborators uses more advanced results.

In distributed computing, a celebrated family of impossibility results was derived using methods of algebraic topology (See the work of Maurice Herlihy and Nir Shavit).

[Edit: See [Applications of Topology to Computer Science](https://cstheory.stackexchange.com/questions/2898/applications-of-topology-to-computer-science).]


---

### Answer by username_8 on 2012-05-06. Score: 13

Rings, modules, and algebraic varieties are used in error correction and, more generally, coding theory.

Specifically, there is an abstract error correcting scheme (algebraic-geometry codes) which generalizes Reed-Solomon codes and Chinese Remainder codes. The scheme is basically to take your messages to come from a ring R and encode it by taking its residues modulo many different ideals in R. Under certain assumptions about R, one can prove that this makes a decent error correcting code.

In the world of list decoding, a recent [paper](http://arxiv.org/pdf/1106.0436.pdf) by Guruswami gives an linear-algebraic method of list decoding folded Reed-Solomon codes, which has the nice property that all of the candidate messages lie in a low-dimensional affine subspace of the message space. One can construct **subspace evasive sets**, sets which are almost as large as the whole space but have small intersection with every low-dimensional affine subspace. If one restricts messages to come from a subspace evasive set inside the message space, then Guruswami's scheme gives an algorithm that guarantees nice list size. So far the only explicit construction of subspace evasive sets is given by Dvir and Lovett in their upcoming STOC paper, [Subspace Evasive Sets](http://arxiv.org/pdf/1110.5696.pdf) and construct the set by taking a specific affine variety (and taking its Cartesian product with itself).


---

### Answer by username_9 on 2012-03-31. Score: 12

Here are two applications from a different part of TCS.

Semirings are used for modelling annotations in databases (especially those needed for provenance), and often also for the valuation structures in valued constraint satisfaction. In both of these applications, individual values must be combined together in ways which lead naturally to a semiring structure, with associativity and the one semiring operation distributing over the other. Regarding your query about modules, neither monoid has an inverse in these applications, in general.

* Todd J. Green, Grigoris Karvounarakis and Val Tannen. *Provenance semirings*, PODS 2007. [doi:10.1145/1265530.1265535](http://dx.doi.org/10.1145/1265530.1265535) ([preprint](http://www.ics.forth.gr/~gregkar/publications/pods2007.pdf))
* Stefano Bistarelli, Ugo Montanari and Francesca Rossi. *Semiring-based constraint satisfaction and optimization*, JACM 1997. [doi:10.1145/256303.256306](http://dx.doi.org/10.1145/256303.256306) ([preprint](http://www.math.unipd.it/~frossi/jacm.pdf))


---

### Answer by username_13 on 2015-12-27. Score: 8

Algebra (and algebraic geometry) has had a pretty big role to play in cryptography, with elliptic curve groups, (number-theoretic) lattices, and of course $\mathbb{Z}\_p$ being the basis for nearly all modern cryptographic work.

> **Comments:**
> **username_14**: As I understand, there are other algebraic structures (finite fields, rings, and other structures) being used in modern Crypto -- which is gradually abandoning number theory and focusing more on lattices, error-correcting codes and "quantum-resistant" problems.  

---

### Answer by username_15 on 2012-03-30. Score: 6

Analyzing any problem with a lot of symmetry is facilitated by using group theory. An example would be to find algorithms for things like rubic's cube. Although I do not know the details, I am sure that proving that [God's number is 20](http://www.cube20.org/) required some serious group theoretical pruning. In a different context, practical solvers for graph isomorphism problem like [nauty](http://cs.anu.edu.au/~bdm/nauty/) use the automorphism group of the graph.

> **Comments:**
> **username_16**: Also, the algorithms for graph isomorphism [Luks '81; Babai--Luks '82] with the best-known guarantees (that is, works in theory, but may be inefficient in practice) use group theory heavily, even invoking the classification of finite simple groups.  

---

### Answer by username_17 on 2012-03-30. Score: 6

Check out *Ramsey Theory* -- basically a significant generalization of the *pigeonhole principle* which underlies a lot of automata and formal language theory (or should I say, the pigeonhole principle is the simplest case of Ramsey Theory). It basically says that even highly disordered structures turn out to necessarily contain a lot of order if they are sufficiently large. For a small example just beyond the pigeonhole principle, note that if you take any six people, then either three of them mutually know each other or three of them mutually do not know each other.

[This paper](http://www.cs.yale.edu/clique/resources/ramsey.pdf) looks like a nice place to start for connections with computer science, but you can google for more. It's more combinatoric than algebraic in its basic nature, but has many applications in algebra and theoretical CS.

And also check out the story of the inventor, [Frank Ramsey](http://en.wikipedia.org/wiki/Frank_P._Ramsey) -- truly a remarkable polymath who made fundamental, even revolutionary contributions in economics and philosophy as well as mathematics, many unappreciated until much later, all before dying at the age of 26 -- just think! In fact, Ramsey's original theorem, the basis of Ramsey Theory, was a mere lemma in a paper with a bigger aim in mathematical logic.

> **Comments:**
> **username_6**: this is classical extremal combinatorics stuff, i am wondering where do you see the connection with algebra? (i don't debate that ramsey theory is a source of great problems and theorems)  
> **username_17**: Well, for one, graph theory is extremely important in theoretical CS.  And check out the link in my answer as well as [this search](https://www.google.com/search?q=ramsey+theory+computer&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a).  Also, from Pin, J.E., _Varieties of formal languages_, Theorem 1.11 -- Any finite semigroup $S$ generated by $A$, $k >= 2$ has $n$ with every word $w \in A^+$ loinger than $n$ having idempotent $e \in S$ with $w = xu_1...u_ny$, $x, y \in A^*$ and all $\bar u_i= e$. This is most easily proved with Ramsey's Theorem.  
> **username_6**: i am not disputing the relevance of ramsey theory, let alone graph theory, to tcs. i am saying that the OP asked about applications of algebra and ramsey theory is not something  usually associated with algebra, afaik. but since you seem to have some connection ramsey theory -> algebra -> tcs in mind, maybe you can add that to your answer  
> **username_17**: @Sasho -- If you mean that Ramsey Theory is not a topic of algebra, so my answer is off-base, then you are 100% correct. I apologize for my answer. I guess my mind tends to cross disciplinary and sub-disciplinary boundaries rather readily.  But it's worse than that -- Ramsey Theory is in no way an "algebraic structure". Please feel free to downvote my answer.  Regards.  
> **username_6**: well while maybe downvoting would be logical, i love extremal combinatorics, so i am not going to :) BTW i am quite sure that there are some ramsey-type phenomena that occur with algebraic structures, maybe even at lower "densities" because of the symmetries, so you're giving me an idea about a question  

---

### Answer by username_18 on 2019-03-18. Score: 2

Recently, we explore (see our paper on springerlink: [A formal series-based unification of the frequent itemset mining approaches](https://link.springer.com/article/10.1007/s10115-017-1048-y)) a unification attempt to pattern mining (a popular instance of data mining) approaches by mean of formal series and weighted automata. These tools are based on mappings between monoids and semiring structures.


---

### Answer by username_19 on 2019-03-19. Score: 2

In functional programming, the most general and elegant abstractions for problems are often algebraic (or category-theoretic) in nature: monoids, [semirings](http://stedolan.net/research/semirings.pdf), functors, monads, F-algebras, F-coalgebras, etc. Some classic results (e.g., the Yoneda lemma) happen to have computational content and utility.

Also, there is homotopy type theory, which interprets type theory in (sort-of) an algebraic topological setting.


---

### Answer by username_20 on 2023-02-22. Score: 1

Most answers on this page are research-oriented. They answer the question: what algebraic structures will help us publish more theoretical papers on computer science. But most of those theoretical papers will not be directly relevant to the work of a software practitioner, even when the programs are written in Haskell or another functional language.

Most frequently, category theory is mentioned as the algebraic structure used in functional programming, so let me comment on that. Category theory has certain but limited use for learning functional programming or in actual practice of functional programming. I recently made a presentation to answer that question. <https://www.youtube.com/watch?v=Zau8CxsfxOo>

Summary:

* Functional programmers do not require category theory in order to master the main features and design patterns that FP uses to write better code. For example, one can (and should) first learn how to use monads, functors, liftings, map/filter/fold, etc., in a concrete programming language with specific examples. Category theory will not help master these techniques even though the words "functor" and "monad" originally come from category theory.
* At a certain point, programmers will encouter examples of typeclasses with laws, and understand why those laws are important in practice.
* There will be lots of laws. To make some order and system among those laws, we can formulate the laws as a generalized "lifting" type signature with "twisted" function types.
* We can then use the definitions of category and functor as generalizations that cover the laws of functors, contrafunctors, filterable functors, filterable contrafunctors, monads, applicative functors, applicative contrafunctors, comonads, and perhaps other type classes.
* I show some examples of categories that are used to describe functors, monads, applicatives, and filterable functors.
* I cover filterable functors in more detail, with backdrop of category theory, because filterable functors are rarely explained as a separate typeclass.
* Another example where category theory is useful: "type constructor libraries", i.e. libraries with functions parameterized by a *type constructor*. Examples of these are free functor / free monad / etc., and Church encoding of types (including recursive type constructors, e.g. the Church encoding of a free monad). Programmers who need to implement these libraries will need to understand how these constructions are defined and what laws need to hold. Category theory provides some limited guidance about that.
* Conclusion 1: programmers need to learn functional programming and not category theory. The special knowledge required in functional programming (e.g., how to implement and use a free applicative functor in your programming language) is not going to be covered by any book in category theory.
* Conclusion 2: basic definitions of category theory (category, functor, natural transformation) are useful as condensed formulations of general laws for a number of typeclasses. Unless a programmer has experience dealing with all the different laws of those typeclasses, it is unlikely that an appreciation of category theory will be of much help. Even for programmers working with high-level type constructor libraries, a study of category theory is unlikely to be of any use beyond a few basic concepts and definitions (category, functor, natural transformation, monoid, initial object, Yoneda identities, F-algebra).
* Conclusion 3: knowledge of category theory will not help us derive or prove laws for specific typeclasses, and will not help us implement those typeclasses correctly in code. The reason is that category theory is so general that it only talks about laws that apply generally to a large number of very different typeclasses (functor, monad, filterable functor, applicative functor, pointed functor, contravariant functor, etc.). For practical coding, e.g. to verify that our implementation of a specific monad is lawful, we need to learn not category theory but the techniques of symbolic derivation and proof.

I am writing a new free textbook ("Science of Functional Programming", <https://github.com/winitzki/sofp>) to develop and explain these techniques with practical programmers in mind. My book is going to be very light on category theory, and I'm not going to use any advanced abstract concepts unless there is a significant gain for practical work. Having written down several hundred step-by-step proofs, I have found what derivation techniques are useful and what definitions from category theory are helpful when proving the theoretical properties of practically relevant code.

Examples of category theory knowledge that has, so far, proved to be unnecessary and **not useful**:

* monad is a monoid in the category of endofunctors
* any monad comes from a pair of adjoint functors
* a free monad comes from the free/forgetful functor adjunction

In contrast, naturality laws are used in about 30% of all proofs, and the functor composition law is also used in around 30% of proofs. This shows the importance of learning the concepts of functor and natural transformation.


---

