The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [group-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
1answer
29 views

Detecting rotational symmetries of spatial structures

I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of ...
4
votes
2answers
59 views

Algorithm for factoring elements of permutation groups?

You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). ...
0
votes
1answer
82 views

Is it possible to interpret some Martin-Löf types as abelian monoids in such a way that any abelian monoid can be represented as a type?

For instance, I can interpret the unit type as the trivial monoid with one element. Non-dependent pairs $A \times B$ can be interpreted as the direct sum $A ⊕ B$ when $A$ and $B$ can both be ...
3
votes
2answers
240 views

Transforming a byte with a subset of a small, fixed set of values and xor into any other value

If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, ...
3
votes
1answer
232 views

How to calculate the minimum number of groups, by grouping groups with capacity together?

I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem. If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
3
votes
1answer
59 views

How to compute quotient subgroup efficiently?

Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group. Model of computation is RAM For all pair of $a$...
1
vote
1answer
113 views

Is finite abelian group isomorphism in Log Space?

Definition : An abelian group is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written Input : Two finite abelian ...
3
votes
1answer
119 views

Representing Integral domains in computer memory?

Earlier I wrote this question about an algorithm computed on an integral domain. However as commented I didn't suggest any particular ways of storing an integral domain in computer memory. I set out ...
1
vote
0answers
71 views

Is there an algorithm for determining whether a element is Prime?

Is there an algorithm that can take an element on an arbitrary integral domain, and determine whether or not it is prime on that ring? It is pretty trivial to do so on a finite integral domain, ...
4
votes
0answers
106 views

Generating all directed multigraphs

I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow ...
6
votes
1answer
335 views

Applications of Graph Automorphisms

I've seen the topic of the automorphism group appear in several introductory graph theory books I've looked at. It always feel oddly disjointed and poorly motivated to me. Is there any practical (or ...
3
votes
1answer
290 views

How to find the symmetry group of a polynomial

Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. ...
0
votes
1answer
60 views

Sifting algorithm for group generated by a set

On page 38 of "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2). I have some confusions. Why it is written that an entry $M_{i,j}, j < i$, cannot ...
3
votes
1answer
102 views

What is the name of the word problem for free groups under straight line program encoding?

I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free ...
1
vote
1answer
20 views

Can you form a group with assembly instructions under the MIPS-32 architecture?

Would it be possible to form such a group using the ADD instruction and the NOT instruction?
5
votes
1answer
124 views

What can be said in general about a homomorphism between two regular languages?

In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can ...
2
votes
1answer
1k views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream $...
0
votes
1answer
79 views

algoritm to convert a monoid into an automaton [closed]

In literature, is there an algoritm to convert a monoid into an atomaton? I am looking for references/applications.
12
votes
2answers
464 views

Group isomorphism to graph ismorphism

In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For ...
2
votes
1answer
195 views

n-Cube as a Cayley Graph

I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how ...
13
votes
4answers
901 views

Bridge theorems for group theory and formal languages

Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines? I am looking for references/applications. However note ...
37
votes
6answers
6k views

What use are groups, monoids, and rings in database computations?

Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird. All I could find is: Implementations of ...
4
votes
1answer
559 views

Visualized definition of cohomology

I cannot imagine how cohomology is related to graph theory, actually I read solid definition from wiki, and to be honest, I cannot understand it. e.g I know what is homotopy (in simple term), group ...