gap-libs 4r7p9-1 / usr / share / gap / lib / fpsemi.gd

#############################################################################
##
#W  fpsemi.gd           GAP library          Andrew Solomon and Isabel Araújo
##
##
#Y  Copyright (C)  1997,  Lehrstuhl D für Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This file contains the declarations for finitely 
##  presented semigroups. 
##


#############################################################################
##
#C  IsElementOfFpSemigroup(<elm>)
##
##  <#GAPDoc Label="IsElementOfFpSemigroup">
##  <ManSection>
##  <Filt Name="IsElementOfFpSemigroup" Arg='elm' Type='Category'/>
##
##  <Description>
##  returns true if <A>elm</A> is an element of a finitely presented semigroup. 
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareCategory( "IsElementOfFpSemigroup",
    IsMultiplicativeElement and IsAssociativeElement );

#############################################################################
##
#O  FpSemigroupOfElementOfFpSemigroup( <elm> )
##
##  <ManSection>
##  <Oper Name="FpSemigroupOfElementOfFpSemigroup" Arg='elm'/>
##
##  <Description>
##  returns the finitely presented semigroup to which <A>elm</A> belongs to
##  </Description>
##  </ManSection>
##
DeclareOperation( "FpSemigroupOfElementOfFpSemigroup",
[IsElementOfFpSemigroup]);

#############################################################################
##
#C  IsElementOfFpSemigroupCollection(<e>)
##
##  <ManSection>
##  <Filt Name="IsElementOfFpSemigroupCollection" Arg='e' Type='Category'/>
##
##  <Description>
##  Created now so that lists of things in the category IsElementOfFpSemigroup
##  are given the category CategoryCollections(IsElementOfFpSemigroup)
##  Otherwise these lists (and other collections) won't create the 
##  collections category. See CollectionsCategory in the manual.
##  </Description>
##  </ManSection>
##
DeclareCategoryCollections("IsElementOfFpSemigroup");

#############################################################################
##
#A  IsSubsemigroupFpSemigroup( <t> )
##
##  <#GAPDoc Label="IsSubsemigroupFpSemigroup">
##  <ManSection>
##  <Attr Name="IsSubsemigroupFpSemigroup" Arg='t'/>
##
##  <Description>
##  true if <A>t</A> is a finitely presented semigroup or a 
##  subsemigroup of a finitely presented semigroup
##  (generally speaking, such a subsemigroup can be constructed
##  with <C>Semigroup(<A>gens</A>)</C>, where <A>gens</A> is a list of elements
##  of a finitely presented semigroup).
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareSynonymAttr( "IsSubsemigroupFpSemigroup", 
	IsSemigroup and IsElementOfFpSemigroupCollection );

#############################################################################
##  
#C  IsElementOfFpSemigroupFamily
##
##  <ManSection>
##  <Filt Name="IsElementOfFpSemigroupFamily" Arg='obj' Type='Category'/>
##
##  <Description>
##  </Description>
##  </ManSection>
##
DeclareCategoryFamily( "IsElementOfFpSemigroup" );

#############################################################################
##
#F  FactorFreeSemigroupByRelations( <f>, <rels> )
##
##  <#GAPDoc Label="FactorFreeSemigroupByRelations">
##  <ManSection>
##  <Func Name="FactorFreeSemigroupByRelations" Arg='f, rels'/>
##
##  <Description>
##  for a free semigroup <A>f</A> and <A>rels</A> is a list of
##  pairs of elements of <A>f</A>. Returns the finitely presented semigroup 
##  which is the quotient of <A>f</A> by the least congruence on <A>f</A> generated by
##  the pairs in <A>rels</A>.
##  <Example><![CDATA[
##  gap> FactorFreeSemigroupByRelations(f,
##  >                            [[s[1]*s[2]*s[1],s[1]],[s[2]^4,s[1]]]);
##  <fp semigroup on the generators [ s1, s2, s3 ]>
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction("FactorFreeSemigroupByRelations");

#############################################################################
##  
#O  ElementOfFpSemigroup( <fam>, <w> )
##
##  <#GAPDoc Label="ElementOfFpSemigroup">
##  <ManSection>
##  <Oper Name="ElementOfFpSemigroup" Arg='fam, w'/>
##
##  <Description>
##  for a family <A>fam</A> of elements of a finitely presented semigroup and 
##  a word <A>w</A> in the free generators underlying this finitely presented
##  semigroup, this operation creates the element of the finitely 
##  presented semigroup with the representative <A>w</A> in the free semigroup.
##  <Example><![CDATA[
##  gap> fam := FamilyObj( GeneratorsOfSemigroup(s)[1] );;
##  gap> ge := ElementOfFpSemigroup( fam, a*b );
##  a*b
##  gap> ge in f;
##  false
##  gap> ge in s;
##  true
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareOperation( "ElementOfFpSemigroup",
    [ IsElementOfFpSemigroupFamily, IsAssocWord ] );

#############################################################################
##
#P  IsFpSemigroup(<s>)
##
##  <#GAPDoc Label="IsFpSemigroup">
##  <ManSection>
##  <Prop Name="IsFpSemigroup" Arg='s'/>
##
##  <Description>
##  is a synonym for <C>IsSubsemigroupFpSemigroup(<A>s</A>)</C> and 
##  <C>IsWholeFamily(<A>s</A>)</C> (this is because a subsemigroup
##  of a finitely presented semigroup is not necessarily finitely presented).
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareSynonym( "IsFpSemigroup",IsSubsemigroupFpSemigroup and IsWholeFamily);

#############################################################################
## 
#A  FreeGeneratorsOfFpSemigroup( <s> )
##
##  <#GAPDoc Label="FreeGeneratorsOfFpSemigroup">
##  <ManSection>
##  <Attr Name="FreeGeneratorsOfFpSemigroup" Arg='s'/>
##
##  <Description>
##  returns the underlying free generators corresponding to the 
##  generators of the finitely presented semigroup <A>s</A>.  
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute("FreeGeneratorsOfFpSemigroup",  IsFpSemigroup );

#############################################################################
## 
#A  FreeSemigroupOfFpSemigroup( <s> )
##
##  <#GAPDoc Label="FreeSemigroupOfFpSemigroup">
##  <ManSection>
##  <Attr Name="FreeSemigroupOfFpSemigroup" Arg='s'/>
##
##  <Description>
##  returns the underlying free semigroup for the finitely presented 
##  semigroup <A>s</A>, ie, the free semigroup over which <A>s</A> is defined 
##  as a quotient
##  (this is the free semigroup generated by the free generators provided 
##  by <C>FreeGeneratorsOfFpSemigroup(<A>s</A>)</C>).
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute("FreeSemigroupOfFpSemigroup", IsFpSemigroup);

############################################################################
##
#A  RelationsOfFpSemigroup(<s>)
##
##  <#GAPDoc Label="RelationsOfFpSemigroup">
##  <ManSection>
##  <Attr Name="RelationsOfFpSemigroup" Arg='s'/>
##
##  <Description>
##  returns the relations of the finitely presented semigroup <A>s</A> as
##  pairs of words in the free generators provided by
##  <C>FreeGeneratorsOfFpSemigroup(<A>s</A>)</C>.
##  <Example><![CDATA[
##  gap> f := FreeSemigroup( "a" , "b" );;
##  gap> a := GeneratorsOfSemigroup( f )[ 1 ];;
##  gap> b := GeneratorsOfSemigroup( f )[ 2 ];;
##  gap> s := f / [ [ a^3 , a ] , [ b^3 , b ] , [ a*b , b*a ] ];
##  <fp semigroup on the generators [ a, b ]>
##  gap> Size( s );
##  8
##  gap> fs := FreeSemigroupOfFpSemigroup( s );;
##  gap> f = fs;
##  true
##  gap> FreeGeneratorsOfFpSemigroup( s );
##  [ a, b ]
##  gap> RelationsOfFpSemigroup( s );
##  [ [ a^3, a ], [ b^3, b ], [ a*b, b*a ] ]
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute("RelationsOfFpSemigroup",IsFpSemigroup);

############################################################################
##
#A  IsomorphismFpSemigroup( <s> )
##
##  <#GAPDoc Label="IsomorphismFpSemigroup">
##  <ManSection>
##  <Attr Name="IsomorphismFpSemigroup" Arg='s'/>
##
##  <Description>
##  for a semigroup <A>s</A> returns an isomorphism from <A>s</A> to a 
##  finitely presented semigroup 
##  <Example><![CDATA[
##  gap> f := FreeGroup(2);;
##  gap> g := f/[f.1^4,f.2^5];
##  <fp group on the generators [ f1, f2 ]>
##  gap> phi := IsomorphismFpSemigroup(g);
##  MappingByFunction( <fp group on the generators 
##  [ f1, f2 ]>, <fp semigroup on the generators 
##  [ <identity ...>, f1^-1, f1, f2^-1, f2 
##   ]>, function( x ) ... end, function( x ) ... end )
##  gap> s := Range(phi);
##  <fp semigroup on the generators [ <identity ...>, f1^-1, f1, f2^-1, 
##    f2 ]>
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareAttribute("IsomorphismFpSemigroup",IsSemigroup);

############################################################################
##
#O  FpGrpMonSmgOfFpGrpMonSmgElement( <elm> )
##
##  <#GAPDoc Label="FpGrpMonSmgOfFpGrpMonSmgElement">
##  <ManSection>
##  <Oper Name="FpGrpMonSmgOfFpGrpMonSmgElement" Arg='elm'/>
##
##  <Description>
##  returns the finitely presented group, monoid or semigroup to which 
##  <A>elm</A> belongs
##  <Example><![CDATA[
##  gap> f := FreeSemigroup("a","b");;
##  gap> a := GeneratorsOfSemigroup( f )[ 1 ];;
##  gap> b := GeneratorsOfSemigroup( f )[ 2 ];;
##  gap> s := f / [ [ a^2 , a*b ] ];;
##  gap> IsFpSemigroup( s );
##  true
##  gap> t := Semigroup( [ GeneratorsOfSemigroup( s )[ 1 ] ]);
##  <semigroup with 1 generator>
##  gap> IsSubsemigroupFpSemigroup( t );
##  true
##  gap> IsElementOfFpSemigroup( GeneratorsOfSemigroup( t )[ 1 ] );
##  true
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareOperation("FpGrpMonSmgOfFpGrpMonSmgElement",[IsMultiplicativeElement]);


#############################################################################
##
#E