请输入您要查询的字词:

 

单词 WordProblem
释义

word problem


Let (X;R) be a presentationMathworldPlanetmathPlanetmathPlanetmath for the group G=GpXR. It is well known that G is a quotient groupMathworldPlanetmath of the free monoid with involution on X, i.e. G=(XX-1)/θ for some congruencePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath θ(XX-1)×(XX-1). We recall that R(XX-1) is a set of words all representing the identityPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 1G of the group, i.e. [r]θ=1G for all rR. The word problem in the category of groups consists in establish whether or not two given words v,w(XX-1) represent the same element of G, i.e. whether or not [v]θ=[w]θ.

Let (X;T) be a presentation for the inverseMathworldPlanetmathPlanetmathPlanetmath monoid M=Inv1XT=(XX-1)/τ, where τ=(ρXT)c. The concept of presentation for inverse monoid is analogous to the group’s one, but now T is a binary relationMathworldPlanetmath on (XX-1), i.e. T(XX-1)×(XX-1).The word problem in the category of inverse monoids consists in establish whether or not two given words v,w(XX-1) represent the same element of M, i.e. whether or not [v]τ=[w]τ.

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. AlgebraMathworldPlanetmathPlanetmath 63 (1990) 81-112.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 0:17:25