# Tag Info

27

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity). By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid). By using Rings, we can do ...

18

Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory. An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with ...

13

Group theory is indeed useful in algorithm design. For example, matrix multiplication is a fundamental problem for which such approaches have been used (see e.g., Cohn et al. [1] or these lecture notes). There are also algebraic algorithms for other problems in e.g., graph theory (Hamiltonian path/cycle, graph motif, and various other path problems) based on ...

12

Let me first answer your subquestion: Does the literature on semiautomata ever look at "group-automata"?. The answer is yes. In his book (Automata, languages, and machines. Vol. B, Academic Press), S. Eilenberg gave a characterization of the regular languages recognized by finite commutative groups and $p$-groups. Similar results are known for finite ...

12

The reduction is described in a classic paper of Miller.

11

Automorphism capture a natural notion of symmetry of graphs. As a result, they can be used to speed up algorithms that would otherwise run slowly by chopping down the search space. For example, integer programming is usually solved via branch-and-bound. However, if an equation is degenerate this can take far longer than necessary to run, because it has to ...

11

Monoids are ubiquitous in programming, just that most programmers don't know about them. Number operations like addition and multiplication. Matrix multiplication. Basically all collection-like data structures form monoids, where the monoidal operation is concatenation or union. This includes lists, sets, maps of keys to values, various kinds of trees etc. ...

11

Barrington's famous theorem reduces computation in NC$^1$ to computing iterated products in the group $S_5$ (or $A_5$, or indeed any non-solvable group). There is also a connection to leakage-resistant computation, in Shielding Circuits with Groups by Miles and Viola (2012). Regarding the classification of the finite simple groups, as far as I remember it ...

10

A famous area of study in the theory of group presentations is the word problem for groups. A group presentation is given by a bunch of generators $g_1, ..., g_m$ and a bunch of equations $a_1 = b_1, ..., a_n = b_n$ that the generated group needs to satisfy. Now given two words $x, y \in \{g_1, ..., g_m\}^*$, i.e. two strings over the alphabet $\{g_1, ..., ... 8 The theory of continuous groups underlies a lot of modern computer graphics and computer vision, because Lie group theory is one of the more natural representations of a space of transformations. Also, Galois theory is one of the workhorses of modern computer algebra systems. 7 One important problem in distributed file systems (DFS) is to generate files from distributed blocks. The area of Erasure code from information theory and Algebra (groups, rings, linear algebra,...) is used extensively in distributed fault tolerant file systems for example in HDFS RAID (Hadoop Based File System). Social network and Cloud companies are ... 6 If your question is What are examples of groups, monoids, and rings in computation? then one example I can think of off-hand is for path-finding algorithms in graph-theory. If we define a semiring with$+$as$\min$and$\cdot$as$+$, then we can use matrix multiplication with the adjacency matrix to find all-pairs-shortest-path. This method is ... 6 Apparently all algebraic topology is useful for is earning imaginary internet points. More than I expected, I guess... (Actually now that I've finished writing I expect to lose points on this...) tl;dr: Honestly, I don't think anyone here can give you an easy way to really understand what homology and cohomology are, with just a short description. I made an ... 6 The answer is to use a de Bruijn sequence, as discussed in response to this question on CS Theory. This gives a sequence of length$10^4=10\,000$. However, the sequence is cyclic, in the sense that if you wrote it on a paper tape and joined the ends together to form a loop, only then would it contain every possible 4-digit sequence and some of those ... 6 Symmetry in combinatorial optimization. An important group-theoretic algorithm often applied in theoretical computer science is Buchberger's algorithm. 5 You have recalled the correct category, "linear-algebra". Let us see how we can interpret xor in the terms of linear-algebra. Here is the computation rules for xor. $$0\oplus0=0$$ $$0\oplus1=1$$ $$1\oplus0=1$$ $$1\oplus1=0$$ If we consider 0 and 1 as the zero element and the unit element of the binary field$\Bbb F_2$, the simplest finite field, then we can ... 5 Some examples, to get the discussion going: For an infinite family of languages with no homomorphisms between them, consider the languages$L_k=\{a,a^k\}\subseteq\{a\}^*$for$k\ge 2$. If$f:L_i\to L_j$were a homomorphism for$i\neq j$, then$f(a)$would be either$a$or$a^j$, and$f(a^i)$would be$a^i$or$a^{ij}$, neither of which is in$L_j$. On the ... 5 Category Theory If you accept Category Theory as a kind of generalization of groups, then we can conclude that modern type theory as related to the design of programming languages absolutely depends on it. For instance, take a look at this Q & A. Also, structures within programming languages, such as monads, are also categories. 4 The set of all words over some finite alphabet together with concatenation forms the free monoid$(\Sigma^*, \cdot)$. Therefore, the whole field of formal language can be viewed through the algebraic lense, and it is sometimes taught like this. In return, considerations on formal languages have yielded the Earley parser which can be extend to parse on ... 4 Not so fast. There is a big lurking ambiguity here: How do you input your group for computation? Unlike graphs, groups can be input be means that are far different in terms of input size and resulting complexity. The version cited in Miller is one of the least natural and for example you wont find that in a computer algebra system such as GAP, Magma, ... 3 Sure. The integers modulo$2^{32}$form a group. The group operation is addition modulo$2^{32}$, which can be implemented by the ADD instruction. You don't need the NOT instruction. There are other groups you could form, such as the integers modulo 2, and many more. I recommend you read the definition of a group and play around with some examples. 3 Short answer. See the Cayley graph of the monoid as an automaton. Details. Let$L$be a language recognised by a finite monoid$M$. Then there is a morphism$\varphi:A^* \rightarrow M$and a subset$P$of$M$such that$L = \varphi^{-1}(P)$. Take the right representation of$A$on$M$defined by$s \cdot a = s\varphi(a)$. This defines a deterministic ... 3 The question is asking you to find a suitable group$\Gamma$and a subset$S$, so that$CG(\Gamma,S)$is the n-cube. Since by definition of$CG$, the nodes are the elements of$\Gamma$, you don't have a choice here, leaving the group operation and$S$.$xy$and the inverse of$y$are then understood with respect to the group operation you choose. Also be ... 3 I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups. These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say). There is rather too much interesting to say. However, it's more a topic of ... 3 You need the eight values to be linearly independent so they form a basis of the space$\{0,1\}^8$. 3 There is a reduction from your problem to graph isomorphism, as explained in this question on Math Overflow. In particular, that answer shows how to obtain a random automorphism of the polynomial, i.e., a random permutation in the symmetric group. For example, you can start by randomly picking a pair of variables$x_i,x_j$and testing whether there exists ... 3 In general this question has no precise answer: the class of integral domains is not even a set, much less a countable set! (For example, for each set$A$, we can find an integral domain$D_A$larger than$A$, e.g.$\mathbb{Z}[A]$, which is sufficient to show that integral domains can't be all gathered into a set). In general you need to specify something ... 3 Dijkstra shortest path algorithm relies heavily on algebraic properties of the way you compare/combine paths (we call it the algebra in this case). Network routing algorithms often use veresions of Dijkstra'a algorithm which are based on a different algebra, and their correctness is guaranteed by the algebraic properties of the compare/combine laws. You can ... 3 To give a yet another example, constraint satisfaction problems can be solved with a semiring formalism, using pretty much schoolbook algebra and lattices. Also, any machine integers are a special case of a residue arithmetic, which is basically,$Z/nZ\$. That's not mentioning all the computer algebra. And formal "muscle" from undergrad algebra ...

2

The blog post you link to already gives a deterministic polynomial-time (in fact, linear-time) algorithm for the word problem over a free group with 2 letters. In contrast, no deterministic polynomial-time algorithm for identity testing for polynomials is currently known (this is a famous open problem). Therefore, it's not likely to be easy to prove that ...

Only top voted, non community-wiki answers of a minimum length are eligible