Concept

Word problem for groups

Related concepts (18)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Group isomorphism problem

In abstract algebra, the group isomorphism problem is the decision problem of determining whether two given finite group presentations refer to isomorphic groups. The isomorphism problem was formulated by Max Dehn, and together with the word problem and conjugacy problem, is one of three fundamental decision problems in group theory he identified in 1911. All three problems are undecidable: there does not exist a computer algorithm that correctly solves every instance of the isomorphism problem, or of the other two problems, regardless of how much time is allowed for the algorithm to run.

Small cancellation theory

In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation conditions imply algebraic, geometric and algorithmic properties of the group. Finitely presented groups satisfying sufficiently strong small cancellation conditions are word hyperbolic and have word problem solvable by Dehn's algorithm.

Coxeter group

In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean reflection groups; the symmetry groups of regular polyhedra are an example. However, not all Coxeter groups are finite, and not all can be described in terms of symmetries and Euclidean reflections. Coxeter groups were introduced in 1934 as abstractions of reflection groups , and finite Coxeter groups were classified in 1935 .

Word problem (mathematics)

In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering this question is in many important cases undecidable. In computer algebra one often wishes to encode mathematical expressions using an expression tree. But there are often multiple equivalent expression trees.

Automatic group

In mathematics, an automatic group is a finitely generated group equipped with several finite-state automata. These automata represent the Cayley graph of the group. That is, they can tell if a given word representation of a group element is in a "canonical form" and can tell if two elements given in canonical words differ by a generator. More precisely, let G be a group and A be a finite set of generators.

Combinatorial group theory

In mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generators and relations. It is much used in geometric topology, the fundamental group of a simplicial complex having in a natural and geometric way such a presentation. A very closely related topic is geometric group theory, which today largely subsumes combinatorial group theory, using techniques from outside combinatorics besides.

Nielsen transformation

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, Nielsen transformations, named after Jakob Nielsen, are certain automorphisms of a free group which are a non-commutative analogue of row reduction and one of the main tools used in studying free groups, . They were introduced in to prove that every subgroup of a free group is free (the Nielsen–Schreier theorem), but are now used in a variety of mathematics, including computational group theory, k-theory, and knot theory.

Burnside problem

The Burnside problem asks whether a finitely generated group in which every element has finite order must necessarily be a finite group. It was posed by William Burnside in 1902, making it one of the oldest questions in group theory and was influential in the development of combinatorial group theory. It is known to have a negative answer in general, as Evgeny Golod and Igor Shafarevich provided a counter-example in 1964.