|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Thomas Breuer, Frank Celler.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains the methods for free semigroups.
##
## Element objects of free semigroups, free monoids and free groups are
## associative words.
## For the external representation see the file 'wordrep.gi'.
##
#############################################################################
##
#M IsWholeFamily( <S> ) . . . . . . . is a free semigroup the whole family
##
## <S> contains the whole family of its elements if and only if all
## magma generators of the family are among the semigroup generators of <S>.
##
InstallMethod( IsWholeFamily,
"for a free semigroup",
[ IsSemigroup and IsAssocWordCollection ],
S -> IsSubset( MagmaGeneratorsOfFamily( ElementsFamily( FamilyObj(S) ) ),
GeneratorsOfMagma( S ) ) );
#############################################################################
##
#M Iterator( <S> ) . . . . . . . . . . . . . . iterator for a free semigroup
##
## Iterator and enumerator of free semigroups are implemented as follows.
## Words appear in increasing length in terms of the generators
## $s_1, s_2, \ldots s_n$.
## So first all words of length 1 are enumerated, then words of length 2,
## and so on.
## There are exactly $n^l$ words of length $l$.
## They are parametrized by $l$-tuples $(c_1, c_2, \ldots, c_l)$,
## corresponding to $s_{c_1} s_{c_2} \cdots s_{c_l}$.
##
## So the word corresponding to the integer
## $m = \sum_{i=1}^{l-1} n^i + m^{\prime}$,
## with $1 \leq m^{\prime} \leq n^l$,
## is the $m^{\prime}$-th word of length $l$.
## Let $m^{\prime} = \sum_{i=1}^l c_i n^{i-1}$, with $1 \leq c_i \leq n$.
## Then this word is $s_{c_1} s_{c_2} \cdots s_{c_l}$.
##
BindGlobal( "FreeSemigroup_NextWordExp", function( iter )
local counter,
len,
pos,
word,
maxexp,
i,
exp;
counter:= iter!.counter;
len:= iter!.length;
pos:= 1;
while counter[ pos ] = iter!.nrgenerators do
pos:= pos + 1;
od;
if pos > len then
# All words of length at most 'len' have been used already.
len:= len + 1;
iter!.length:= len;
counter:= List( [ 1 .. len ], x -> 1 );
Add( counter, 0 );
iter!.counter:= counter;
# The first word of length 'len' is the power of the first generator.
word:= [ 1, len ];
maxexp:= len;
else
# Increase the counter for words of length 'iter!.length'.
for i in [ 1 .. pos-1 ] do
counter[i]:= 1;
od;
counter[ pos ]:= counter[ pos ] + 1;
# Convert the string of generators numbers.
word:= [];
i:= 1;
maxexp:= 1;
while i <= len do
Add( word, counter[i] );
exp:= 1;
while counter[i] = counter[ i+1 ] do
exp:= exp + 1;
i:= i+1;
od;
Add( word, exp );
if maxexp < exp then
maxexp:= exp;
fi;
i:= i+1;
od;
fi;
iter!.word:= word;
iter!.exp:= maxexp;
end );
BindGlobal( "NextIterator_FreeSemigroup", function( iter )
local word;
word:= ObjByExtRep( iter!.family, 1, iter!.exp, iter!.word );
FreeSemigroup_NextWordExp( iter );
return word;
end );
BindGlobal( "ShallowCopy_FreeSemigroup",
iter -> rec(
family := iter!.family,
nrgenerators := iter!.nrgenerators,
exp := iter!.exp,
word := ShallowCopy( iter!.word ),
counter := ShallowCopy( iter!.counter ),
length := iter!.length ) );
InstallMethod( Iterator,
"for a free semigroup",
[ IsAssocWordCollection and IsWholeFamily ],
function( S )
# A free monoid or free group needs another method.
# A trivial monoid/group needs another method.
if IsAssocWordWithOneCollection( S ) or IsTrivial( S ) then
TryNextMethod();
fi;
return IteratorByFunctions( rec(
IsDoneIterator := ReturnFalse,
NextIterator := NextIterator_FreeSemigroup,
ShallowCopy := ShallowCopy_FreeSemigroup,
family := ElementsFamily( FamilyObj( S ) ),
nrgenerators := Length( GeneratorsOfMagma( S ) ),
exp := 1,
word := [ 1, 1 ],
counter := [ 1, 0 ],
length := 1 ) );
end );
#############################################################################
##
#M Enumerator( <S> ) . . . . . . . . . . . . enumerator for a free semigroup
##
BindGlobal( "ElementNumber_FreeMonoid", function( enum, nr )
local n, l, power, word, exp, maxexp, cc, i, c;
if nr = 1 then
return One( enum!.family );
fi;
n:= enum!.nrgenerators;
# Compute the length of the word corresponding to `nr'.
l:= 0;
power:= 1;
nr:= nr - 1;
while 0 < nr do
power:= power * n;
nr:= nr - power;
l:= l+1;
od;
nr:= nr + power - 1;
# Compute the vector of the `(nr + 1)'-th element of length `l'.
exp:= 0;
maxexp:= 1;
c:= nr mod n;
word:= [ c+1 ];
cc:= c;
for i in [ 1 .. l ] do
if c = cc then
exp:= exp + 1;
else
cc:= c;
Add( word, exp );
Add( word, c+1 );
if maxexp < exp then
maxexp:= exp;
fi;
exp:= 1;
fi;
nr:= ( nr - c ) / n;
c:= nr mod n;
od;
if maxexp < exp then
maxexp:= exp;
fi;
Add( word, exp );
# Return the element.
return ObjByExtRep( enum!.family, 1, maxexp, word );
end );
BindGlobal( "ElementNumber_FreeSemigroup", function( enum, nr )
return ElementNumber_FreeMonoid( enum, nr+1 );
end );
BindGlobal( "NumberElement_FreeMonoid", function( enum, elm )
local l, len, i, n, nr, power, c, exp;
if not IsCollsElms( FamilyObj( enum ), FamilyObj( elm ) ) then
return fail;
fi;
elm:= ExtRepOfObj( elm );
l:= Length( elm ) / 2;
# Calculate the length of the word.
len:= 0;
for i in [ 2, 4 .. 2*l ] do
len:= len + elm[i];
od;
# Calculate the number of words of smaller length, plus 1.
n:= enum!.nrgenerators;
nr:= 1;
power:= 1;
for i in [ 1 .. len ] do
nr:= nr + power;
power:= power * n;
od;
# Add the position in the words of length 'len'.
power:= 1;
for i in [ 2, 4 .. 2*l ] do
c:= elm[ i-1 ] - 1;
for exp in [ 1 .. elm[i] ] do
nr:= nr + c * power;
power:= power * n;
od;
od;
return nr;
end );
BindGlobal( "NumberElement_FreeSemigroup", function( enum, elm )
local nr;
nr:= NumberElement_FreeMonoid( enum, elm );
if nr <> fail then
nr:= nr - 1;
fi;
return nr;
end );
InstallMethod( Enumerator,
"for a free semigroup",
[ IsAssocWordCollection and IsWholeFamily and IsSemigroup ],
function( S )
# A free monoid or free group needs another method.
# A trivial semigroup/monoid/group needs another method.
if IsAssocWordWithOneCollection( S ) or IsTrivial( S ) then
TryNextMethod();
fi;
return EnumeratorByFunctions( S, rec(
ElementNumber := ElementNumber_FreeSemigroup,
NumberElement := NumberElement_FreeSemigroup,
family := ElementsFamily( FamilyObj( S ) ),
nrgenerators := Length( ElementsFamily(
FamilyObj( S ) )!.names ) ) );
end );
#############################################################################
##
#M IsFinite( <S> ) . . . . . . . . . . . . . for a semigroup of assoc. words
##
InstallMethod( IsFinite,
"for a semigroup of assoc. words",
[ IsSemigroup and IsAssocWordCollection ],
IsTrivial );
#############################################################################
##
#M Size( <S> ) . . . . . . . . . . . . . . . . . . size of a free semigroup
##
InstallMethod( Size,
"for a free semigroup",
[ IsSemigroup and IsAssocWordWithOneCollection ],
function( S )
if IsTrivial( S ) then
return 1;
else
return infinity;
fi;
end );
#
# I suspect this methos subsumes the one above SL
#
InstallImmediateMethod(Size, IsSemigroup and IsAssocWordCollection
and HasGeneratorsOfMagma, 0, function(s)
local x, gens;
gens := GeneratorsOfMagma(s);
if Length(gens) = 0 then
return 0;
fi;
for x in gens do
if Length(x) > 0 then
return infinity;
fi;
od;
return 1;
end);
#############################################################################
##
#M Random( <S> ) . . . . . . . . . . . . random element of a free semigroup
##
#T use better method for the whole family
##
InstallMethodWithRandomSource(Random,
"for a random source and a free semigroup",
[ IsRandomSource, IsSemigroup and IsAssocWordCollection ],
function( rs, S )
local len, result, gens, i;
# Get a random length for the word.
len:= Random( rs, Integers );
if 0 <= len then
len:= 2 * len;
else
len:= -2 * len - 1;
fi;
# Multiply $'len' + 1$ random generators.
gens:= GeneratorsOfMagma( S );
result:= Random( rs, gens );
for i in [ 1 .. len ] do
result:= result * Random( rs, gens );
od;
# Return the result.
return result;
end );
#############################################################################
##
#M MagmaGeneratorsOfFamily( <F> )
##
InstallMethod( MagmaGeneratorsOfFamily,
"for a family of free semigroup elements",
[ IsAssocWordFamily ],
F -> List( [ 1 .. Length( F!.names ) ],
i -> ObjByExtRep( F, 1, 1, [ i, 1 ] ) ) );
# GeneratorsOfSemigroup returns the generators in ascending order
InstallMethod( GeneratorsSmallest,
"for a free semigroup",
[ IsFreeSemigroup ],
GeneratorsOfSemigroup);
#############################################################################
##
#F FreeSemigroup( [<wfilt>, ]<rank>[, <name>] )
#F FreeSemigroup( [<wfilt>, ]<name1>[, <name2>[, ...]] )
#F FreeSemigroup( [<wfilt>, ]<names> )
#F FreeSemigroup( [<wfilt>, ]infinity[, <name>][, <init>] )
##
InstallGlobalFunction( FreeSemigroup, function( arg )
local rank, # number of generators
F, # family of free semigroup element objects
S, # free semigroup, result
processed;
processed := FreeXArgumentProcessor( "FreeSemigroup", "s", arg, true, false );
rank := Length( processed.names );
# Construct the family of element objects of our semigroup.
F := NewFamily( "FreeSemigroupElementsFamily",
IsAssocWord,
CanEasilySortElements,
CanEasilySortElements and processed.lesy );
# Install the data (names, no. of bits available for exponents, types).
StoreInfoFreeMagma( F, processed.names, IsAssocWord );
# Make the semigroup.
if rank < infinity then
S:= SemigroupByGenerators( MagmaGeneratorsOfFamily( F ) );
else
S:= SemigroupByGenerators( InfiniteListOfGenerators( F ) );
fi;
# store the whole semigroup in the family
FamilyObj(S)!.wholeSemigroup:= S;
F!.freeSemigroup:=S;
SetIsFreeSemigroup( S, true );
SetIsWholeFamily( S, true );
SetIsTrivial( S, false );
# Following is written defensively in case 0-generator free semigroups ever
# become supported in the future.
SetIsFinite( S, rank = 0 );
SetIsEmpty( S, rank = 0 );
SetIsCommutative( S, rank <= 1 );
return S;
end );
#############################################################################
##
#M ViewObj( <S> ) . . . . . . . . . . . . . . . . . . for a free semigroup
##
InstallMethod( ViewObj,
"for a free semigroup containing the whole family",
[ IsSemigroup and IsAssocWordCollection and IsWholeFamily ],
function( S )
if GAPInfo.ViewLength * 10 < Length( GeneratorsOfMagma( S ) ) then
Print( "<free semigroup with ", Length( GeneratorsOfMagma( S ) ),
" generators>" );
else
Print( "<free semigroup on the generators ",
GeneratorsOfMagma( S ), ">" );
fi;
end );
[ Dauer der Verarbeitung: 0.26 Sekunden
(vorverarbeitet)
]
|
