PlanetMath: word problem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (21)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

word problem

(Definition)

Let be a presentation for the group $G=\mathrm{Gp}\left\langle X \vert R \right\rangle$ . It is well known that is a quotient group of the free monoid with involution on , 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 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 , i.e. whether or not $[v]_\theta=[w]_\theta$ .

Let be a presentation for the inverse monoid $M=\mathrm{Inv}^1\left\langle X \vert 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 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 , 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.

Bibliography

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.

"word problem" is owned by Mazzu.

(view preamble | get metadata)

Also defines:

word problem

Keywords:

inverse semigroup, presentation

Log in to rate this entry.
(view current ratings)

Cross-references: inverse semigroups, binary relation, monoid, represent, category, identity, words, congruence, free monoid with involution, quotient group, group, presentation
There are 4 references to this entry.

This is version 6 of word problem, born on 2006-08-27, modified 2006-08-28.
Object id is 8301, canonical name is InverseMonoidsAndInverseSemigroupsWordProblemInTheCategoryOfGroups.
Accessed 1955 times total.

Classification:

AMS MSC:	20M05 (Group theory and generalizations :: Semigroups :: Free semigroups, generators and relations, word problems)
	20M18 (Group theory and generalizations :: Semigroups :: Inverse semigroups)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact