Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
8  
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 Mar 30 '12 at 21:02
2  
Possibly anything that can be representable has an use in Computer Science! –  v s Mar 30 '12 at 21:36
    

10 Answers 10

up vote 29 down vote accepted

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.

share|improve this answer
17  
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. –  JɛffE Mar 31 '12 at 11:38
4  
there is plenty of interaction between topology and algebra in pure math... –  Sasho Nikolov Mar 31 '12 at 16:06
10  
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 Apr 2 '12 at 21:48
3  
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 Apr 6 '12 at 15:40
3  
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 Apr 6 '12 at 15:46

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.

share|improve this answer
2  
+1: and many consider it as one of the most surprising results in complexity theory. :) –  Kaveh Mar 31 '12 at 6:15

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.

share|improve this answer
    
@JeffE, links, please. –  scaaahu Mar 31 '12 at 9:43
1  
@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. –  scaaahu Mar 31 '12 at 12:03
    
I suggest starting with this paper. (Sorry, my earlier comment was uncalled for.) –  JɛffE Mar 31 '12 at 12:10
    
@JeffE, got it, exactly what I was looking for. Thanks. –  scaaahu Mar 31 '12 at 12:16

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.

share|improve this answer
    
Thanks for the pointer and overview! This was from FOCS 2011: dx.doi.org/10.1109/FOCS.2011.55 –  András Salamon Mar 31 '12 at 16:17

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
2  
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 Apr 3 '12 at 3:59
    
Well, for one, graph theory is extremely important in theoretical CS. And check out the link in my answer as well as this search. 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 Apr 3 '12 at 11:14
    
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 Apr 3 '12 at 14:07
    
@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 Apr 3 '12 at 18:54
    
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 Apr 3 '12 at 20:06

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.

share|improve this answer
    
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 May 8 '12 at 16:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.