## You are here

Homeword problem

## Primary tabs

# word problem

Let $(X;R)$ be a presentation^{} for the group $G=\mathrm{Gp}\left\langle X\mid R\right\rangle$. It is well known that $G$ is a quotient group of the free monoid with involution on $X$, i.e. $G=\left(X\amalg X^{{-1}}\right)^{\ast}/\theta$ for some congruence^{} $\theta\subseteq\left(X\amalg X^{{-1}}\right)^{\ast}\times\left(X\amalg X^{{-1}%
}\right)^{\ast}$. We recall that $R\subset\left(X\amalg 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\amalg 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}\left\langle X\mid T\right\rangle=\left(X\amalg 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\amalg X^{{-1}}\right)^{\ast}$, i.e. $T\subseteq\left(X\amalg X^{{-1}}\right)^{\ast}\times\left(X\amalg 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\amalg 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.

# References

- 1
W. W. Boone,
*Certain simple unsolvable problems in group theory*, I, II, III, IV, V, VI, Nederl. Akad.Wetensch Proc. Ser. A57, 231-237,492- 497 (1954), 58, 252-256,571-577 (1955), 60, 22-27,227-232 (1957). - 2
R. Lyndon and P. Schupp,
*Combinatorial Group Theory*, Springer-Verlag, 1977. - 3
P.S. Novikov,
*On the algorithmic unsolvability of the word problem in group theory*, Trudy Mat. Inst. Steklov 44, 1-143 (1955). - 4
J.B. Stephen,
*Presentation of inverse monoids*, J. Pure Appl. Algebra^{}63 (1990) 81- 112.

## Mathematics Subject Classification

20M18*no label found*20M05

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Lorenz system by David Bankom

Oct 19

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag

Sep 26

new question: Latent variable by adam_reith