Word problem for groups

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.

About this result

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 (1)

Related concepts (25)

Related courses (5)

Related lectures (17)

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.

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.

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.

On Polynomial Algorithms for Normalizing Formulas

Viktor Kuncak, Simon Guilloud, Mario Bucev

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem for two subtheories of Boolean algebra, giving a sound procedure for propositional logical equivalence that is incomplete in general but complete with respect to a subset of Boolean algebra axioms. We first show a new algorithm to produce a normal form for expressions in the theory of ortholattices (OL) in time O(n^2). We also consider an algorithm, recently presented but never evaluated in practice, producing a normal form for a slightly weaker theory, orthocomplemented bisemilattices (OCBSL), in time O(n log(n)^2). For both algorithms, we present an implementation and show efficiency in two domains. First, we evaluate the algorithms on large propositional expressions, specifically combinatorial circuits from a benchmark suite, as well as on large random formulas. Second, we implement and evaluate the algorithms in the Stainless verifier, a tool for verifying the correctness of Scala programs. We used these algorithms as a basis for a new formula simplifier, which is applied before valid verification conditions are saved into a persistent cache. The results show that normalization substantially increases cache hit ratio in large benchmarks.

2022

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,

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 CS-101: Advanced information, computation, communication I

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

Halting Problem: Unsolvable Problems CS-101: Advanced information, computation, communication I

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