Uses of algebraic structures in theoretical computer science

Question

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?

Answer 1

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, 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. 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 and then generalized them to domains. 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. 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 and algebraic theories of effects. Coalgebras, 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.

Answer 2

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, and Barrington's exposition in the comment section of that post.

Answer 3

Groups, rings, fields, and modules are everywhere in computational topology. See especially Carlsson and Zomorodian's work [ex: 1] on (multidimensional) persistent homology, which is all about graded modules over principal ideal domains.

Answer 4

Here is a very nice, practical use: an algorithm for computing graph connectivity (from FOCS2011). 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.

Answer 5

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 6

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.]

Answer 7

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 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 and construct the set by taking a specific affine variety (and taking its Cartesian product with itself).

Answer 8

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 (preprint)
• Stefano Bistarelli, Ugo Montanari and Francesca Rossi. Semiring-based constraint satisfaction and optimization, JACM 1997. doi:10.1145/256303.256306 (preprint)

Answer 9

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.

Answer 10

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 required some serious group theoretical pruning. In a different context, practical solvers for graph isomorphism problem like nauty use the automorphism group of the graph.

Answer 11

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 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 -- 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.

Answer 12

Recently, we explore (see our paper on springerlink: A formal series-based unification of the frequent itemset mining approaches) 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 13

In functional programming, the most general and elegant abstractions for problems are often algebraic (or category-theoretic) in nature: monoids, semirings, 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 14

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.