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


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


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


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


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


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


2

The finite abelian group-isomorphism when groups are given in the form of multiplication tables known to be in $L$ and in $TC^0 (FOLL)$. For more detail you can see the thesis of the Dr. Fabian. PhD Thesis of Dr. Fabian ( see page number 180 and 185 )


2

Let $S$ be a set of generators in $S_n$ such that $S$ is closed under inverses, and let $h \in S_n$. The goal is to express $h$ as a product of elements of $S$. A graph-theoretic approach to solve this problem is to construct the Cayley digraph of $S_n$ with respect to generating set $S$, denoted $G = Cay(S_n,S)$, which is defined to be the graph with ...


2

It seems that your problem could be stated in terms of finding paths in Cayley Graphs, which might interest you: Cayley Graph - Wikipedia


2

The subset sum problem is even harder(NP-hard) for special groups which you can embed into $S_n$. See the paper you have linked in the problem description. $\textbf{Observation:}$ $g$ can be writtens as combination of elements $\{g_1,\ldots,g_k\}$ if and only if $g \in \langle g_1,\ldots,g_k\rangle$. Under the assumption that each of $g_i$ can appears any ...


1

Here is one approach to identify all rotational symmetries of the graph: Pick any three vertices, $v_1,\dots,v_3$. Loop over all possible combinations of three vertices $w_1,\dots,w_3$. For each such combination, find the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, then check whether this is a rotational symmetry of the entire ...


1

The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem. If car A has a higher capacity than car B, and you get an optimal solution (smallest number of cars) containing B but not A, then you can swap cars A and B, you won't need more cars, and because A has more empty capacity, you ...


1

Based on the following snippet from https://en.wikipedia.org/wiki/Quotient_group: In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup. It seems that you can simply set $H$ to be the identity element of $...


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