**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Word problem for groups

Summary

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if A is a finite set of generators for G then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G. If B is another finite generating set for G, then the word problem over the generating set B is equivalent to the word problem over the generating set A. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G.
The related but different uniform word problem for a class K of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P for a group G in the class K and two words in the generators of G, whether the words represent the same element of G. Some authors require the class K to be definable by a recursively enumerable set of presentations.
Throughout the history of the subject, computations in groups have been carried out using various normal forms. These usually implicitly solve the word problem for the groups in question. In 1911 Max Dehn proposed that the word problem was an important area of study in its own right, together with the conjugacy problem and the group isomorphism problem. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2. Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems.
It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group G such that the word problem for G is undecidable. It follows immediately that the uniform word problem is also undecidable.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (33)

Related concepts (18)

Related courses (5)

Related people (1)

Related lectures (17)

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs.

Group theory

In abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen as groups endowed with additional operations and axioms. Groups recur throughout mathematics, and the methods of group theory have influenced many parts of algebra. Linear algebraic groups and Lie groups are two branches of group theory that have experienced advances and have become subject areas in their own right.

Max Dehn

Max Wilhelm Dehn (November 13, 1878 – June 27, 1952) was a German mathematician most famous for his work in geometry, topology and geometric group theory. Dehn's early life and career took place in Germany. However, he was forced to retire in 1935 and eventually fled Germany in 1939 and emigrated to the United States. Dehn was a student of David Hilbert, and in his habilitation in 1900 Dehn resolved Hilbert's third problem, making him the first to resolve one of Hilbert's well-known 23 problems.

ENG-626: Ma thèse en 180 secondes

The aim of the course is to improve the students communication skills. They will learn to summarize the methodology and conclusions of their thesis in 180 seconds and communicate clearly, accurately,

HUM-451: Artistic practices - field ftudies, film practice II

Ce cours, propose 2 options, en anglais et en français : 'Elsewhere Encounters' propose d'explorer différentes approches de la cartographie dans le monde artistique ; 'Réalisation' se penche sur les t

HUM-401: Artistic practices I

Ce cours, propose 2 options, en anglais et en français : 'Elsewhere Encounters' propose d'explorer différentes approches de la cartographie dans le monde artistique ; 'Réalisation' se penche sur les t

Endomorphisms and automorphisms of totally disconnected locally compact groups II

Explores flat groups of automorphisms and their properties, including minimization functions and invariance under specific conditions.

Algorithms & Growth of Functions

Covers optimization algorithms, stable matching, and Big-O notation for algorithm efficiency.

Halting Problem: Unsolvable Problems

Explores the halting problem, demonstrating its unsolvability and the limitations of algorithms.

This text, accompanied by a ‘gospel’ that I made by montaging the US-recorded captions, is an attempt for re-narrating Marshall Plan’s discourse on the working class, aka the so-called ‘free labor’ of the US against the ‘communist labor’ of the “Soviet thr ...

, ,

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

,

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...