word problem

Let $(X;R)$ be a presentation for the group $G=\mathrm{Gp}⟨X\mid R⟩$. It is well known that $G$ is a quotient group of the free monoid with involution on $X$, i.e. $G={\left(X\coprod X^{-1}\right)}^{\ast }/\theta$ for some congruence $\theta \subseteq {\left(X\coprod X^{-1}\right)}^{\ast }\times {\left(X\coprod X^{-1}\right)}^{\ast }$. We recall that $R\subset {\left(X\coprod X^{-1}\right)}^{\ast }$ is a set of words all representing the identity $1_G$ of the group, i.e. ${[r]}_{\theta }=1_G$ for all $r\in R$. The word problem in the category of groups consists in establish whether or not two given words $v,w\in {\left(X\coprod X^{-1}\right)}^{\ast }$ represent the same element of $G$, i.e. whether or not ${[v]}_{\theta }={[w]}_{\theta }$.

Let $(X;T)$ be a presentation for the inverse monoid $M={\mathrm{Inv}}^1⟨X\mid T⟩={\left(X\coprod X^{-1}\right)}^{\ast }/\tau$, where $\tau ={({\rho }_X\cup T)}^{\mathrm{c}}$. The concept of presentation for inverse monoid is analogous to the group’s one, but now $T$ is a binary relation on ${\left(X\coprod X^{-1}\right)}^{\ast }$, i.e. $T\subseteq {\left(X\coprod X^{-1}\right)}^{\ast }\times {\left(X\coprod X^{-1}\right)}^{\ast }$. The word problem in the category of inverse monoids consists in establish whether or not two given words $v,w\in {\left(X\coprod X^{-1}\right)}^{\ast }$ represent the same element of $M$, i.e. whether or not ${[v]}_{\tau }={[w]}_{\tau }$.

We can modify the last paragraph to introduce the word problem in the category of inverse semigroups as well.

A classical results in combinatorial group theory says that the word problem in the category of groups is undecidable, so it is undecidable also for the larger categories of inverse semigroups and inverse monoids.

Title	word problem
Canonical name	WordProblem
Date of creation	2013-05-17 17:00:19
Last modified on	2013-05-17 17:00:19
Owner	Mazzu (14365)
Last modified by	unlord (1)
Numerical id	11
Author	Mazzu (1)
Entry type	Definition
Classification	msc 20M18
Classification	msc 20M05
Defines	word problem