Munn tree


Let X be a finite set, and (XX-1) the free monoid with involution on X. It is well known that the elements of (XX-1) can be viewed as words on the alphabet (XX-1), i.e. as elements of the free monod on (XX-1).

The Munn tree of the word w(XX-1) is the X-inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath word graph MT(w) (or MTX(w) if X needs to be specified) with vertex and edge set respectively

V(MT(w))=red(pref(w))={red(v)|vpref(w)},
E(MT(w))={(v,x,red(vx))V(MT(w))×(XX-1)×V(MT(w))}.

The concept of Munn tree was created to investigate the structureMathworldPlanetmath of the free inverse monoid. The main result about it says that it “recognize” whether or not two different word in (XX-1) belong to the same ρX-class, where ρX is the Wagner congruence on X. We recall that if w(XX-1) [resp. w(XX-1)+], then [w]ρXFIM(X) [resp. [w]ρXFIS(X)].

Theorem 1 (Munn)

Let v,w(XX-1) (or v,w(XX-1)+). Then [v]ρX=[w]ρX if and only if MT(v)=MT(w)

As an immediate corollary of this result we obtain that the word problem in the free inverse monoid (and in the free inverse semigroup) is decidable. In fact, we can effectively build the Munn tree of an arbitrary word in (XX-1), and this suffice to prove wheter or not two words belong to the same ρX-class.

The Munn tree reveals also some property of the -classes of elements of the free inverse monoid, where is the right Green relation. In fact, the following result says that “essentially” the Munn tree of w(XX-1) is the Schützenberger graph of the -class of [w]ρX.

Theorem 2

Let w(XX-1). There exists an isomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath (in the category of X-inverse word graphs) Φ:MT(w)SΓ(X;;[w]ρX) between the Munn tree MT(w) and the Schützenberger graph SΓ(X;;[w]ρX) given by

ΦV(v)=[v]ρX,vV(MT(w))=red(pref(w)),
ΦE((v,x,red(vx)))=([v]ρX,x,[vx]ρX),(v,x,red(vx))E(MT(w)).

References

  • 1 W.D. Munn, Free inverse semigroups, Proc. London Math. Soc. 30 (1974) 385-404.
  • 2 N. Petrich, Inverse Semigroups, Wiley, New York, 1984.
  • 3 J.B. Stephen, PresentationMathworldPlanetmathPlanetmathPlanetmath of inverse monoids, J. Pure Appl. AlgebraMathworldPlanetmathPlanetmathPlanetmath 63 (1990) 81-112.
Title Munn tree
Canonical name MunnTree
Date of creation 2013-03-22 16:11:59
Last modified on 2013-03-22 16:11:59
Owner Mazzu (14365)
Last modified by Mazzu (14365)
Numerical id 20
Author Mazzu (14365)
Entry type Definition
Classification msc 20M05
Classification msc 20M18
Related topic SchutzenbergerGraph
Defines Munn tree