Quelle tietze.gi Sprache: unbekannt

#############################################################################
##
##  This file is part of GAP, a system for computational discrete algebra.
##  This file's authors include Volkmar Felsch.
##
##  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 Tietze transformations of presentation
##  records (i.e., of presentations of finitely presented groups (fp groups).
##

#############################################################################
##
#F  TzTestInitialSetup(<Tietze object>)
##
##  This function calls TzHandleLength1Or2Relators on a presentation for
##  which is has not yet been called. (Needed because we cannot yet call it
##  while the presentation is created, as it may remove generators.)
BindGlobal( "TzTestInitialSetup", function( T )
  if not IsBound( T!.hasRun1Or2 ) then
    TzHandleLength1Or2Relators( T );
    T!.hasRun1Or2:=true;
    TzSort( T );
  fi;
end );

#############################################################################
##
#M  AddGenerator( <Tietze record> )  . . . . . . . . . . . .  add a generator
##
##  extends the given Tietze presentation by a new generator.
##
##  Let i be the smallest positive integer which has not yet been used as
##  a generator number and for which no component T!.i exists so far in the
##  given presentation T. `AddGenerator' defines a new abstract
##  generator _xi and adds it, as component T!.i, to the given presentation.
##
InstallGlobalFunction( AddGenerator, function ( T )

    local gen, numgens, tietze;

    # check the given argument to be a Tietze record.
    TzCheckRecord( T );

    # define an abstract generator and add it to the set of generators.
    gen := TzNewGenerator( T );

    # display a message.
    if TzOptions(T).printLevel >= 1 then
        tietze := T!.tietze;
        numgens := tietze[TZ_NUMGENS];
        Print( "#I  now the presentation has ", numgens,
            " generators, the new generator is ", gen, "\n");
    fi;

    # if there is a tree of generators, delete it.
    if IsBound( T!.tree ) then  Unbind( T!.tree );  fi;

    # if generator images and preimages are being traced through the
    # Tietze transformations applied to T, delete them.
    if IsBound( T!.imagesOldGens ) then
        TzUpdateGeneratorImages( T, -1, 0 );
    fi;

    tietze[TZ_MODIFIED] := true;
    tietze[TZ_OCCUR]:=false;
end );

#############################################################################
##
#M  AddRelator( <Tietze record>, <word> )  . . . . . . . . . .  add a relator
##
##  adds the given relator to the given Tietze presentation.
##
InstallGlobalFunction( AddRelator, function ( T, word )

    local flags, leng, lengths, numrels, rel, rels, tietze;

    # check the first argument to be a Tietze record.
    TzCheckRecord( T );

    if TzOptions(T).printLevel >= 3 then
        Print( "#I  adding relator ",word,"\n" );
    fi;

    tietze := T!.tietze;
    rels := tietze[TZ_RELATORS];
    numrels := tietze[TZ_NUMRELS];
    flags := tietze[TZ_FLAGS];
    lengths := tietze[TZ_LENGTHS];

    # add rel to the relators of T, and make the Tietze lists consistent.
    rel := TzRelator( T, word );
    leng := Length( rel );
    if leng > 0 then
        numrels := numrels + 1;
        rels[numrels] := rel;
        lengths[numrels] := leng;
        flags[numrels] := 1;
        tietze[TZ_NUMRELS] := numrels;
        tietze[TZ_TOTAL] := tietze[TZ_TOTAL] + leng;
        tietze[TZ_MODIFIED] := true;
        tietze[TZ_OCCUR]:=false;
    fi;
end );

#############################################################################
##
#M  TzRelatorOldImages( <Tietze record>, <word> )  . . . . .  rewrite relator
##
##  adds the given relator, possibly in old generators, write it in the
##  current generators.
## to the given Tietze presentation.
##
InstallGlobalFunction( TzRelatorOldImages, function ( T, word )

local flags, leng, lengths, numrels, rel, rels, tietze,l,imgs,i,j,a,fam;

    # do we need to translate?
    if IsBound(T!.imagesOldGens) then
      imgs:=T!.imagesOldGens;
      l:=word^0;
      for i in LetterRepAssocWord(word) do
        if i<0 then
          a:=-Reversed(imgs[-i]);
        else
          a:=imgs[i];
        fi;
        for j in a do
          if j>0 then
            l:=l*T!.generators[j];
          else
            l:=l/T!.generators[-j];
          fi;
        od;
      od;

      word:=l;

    fi;
    return word;
end );

#############################################################################
##
#M  DecodeTree( <Tietze record> )  . . . .  decode a subgroup generators tree
##
##  `DecodeTree'  applies the tree decoding method to a subgroup presentation
##  provided by the  Reduced Reidemeister-Schreier  or by the  Modified Todd-
##  Coxeter method.
##
##  rels    is the set of relators.
##  gens    is the set of generators.
##  total   is the total length of all relators.
##
InstallGlobalFunction( DecodeTree, function ( T )

    local count, decode, looplimit, primary, protected, tietze, trlast;

    # check the given argument to be a Presentation.
    if not IsPresentation( T ) then
        Error( "argument must be a Presentation" );
    fi;
    tietze := T!.tietze;
    protected := TzOptions(T).protected;

    # check if there is a tree of generators.
    if not IsBound( T!.tree ) then
        Error( "there is not tree to decode it" );
    fi;
    decode := true;
    TzOptions(T).protected := Maximum( protected, T!.tree[TR_PRIMARY] );

    # if generator images are being traced, delete them.
    if IsBound( T!.imagesOldGens ) then
        Unbind( T!.imagesOldGens );
    fi;

    # substitute substrings by shorter ones.
    TzSearch( T );

    # now run our standard strategy and repeat it.
    looplimit := TzOptions(T).loopLimit;
    count := 0;
    while count < looplimit and tietze[TZ_TOTAL] > 0 do

        # replace substrings by substrings of equal length.
        TzSearchEqual( T );
        if tietze[TZ_MODIFIED] then  TzSearch( T );  fi;

        # eliminate generators.
        TzEliminateGens( T, decode  );
        if tietze[TZ_MODIFIED] then
            TzSearch( T );
            if tietze[TZ_MODIFIED] then  TzSearch( T );  fi;
            if tietze[TZ_MODIFIED] then  TzSearchEqual( T );  fi;
            if tietze[TZ_MODIFIED] then  TzSearch( T );  fi;
            count := count + 1;
        else
            count := looplimit;
        fi;

        if TzOptions(T).printLevel = 1 then  TzPrintStatus( T, true );  fi;
    od;

    # check if the tree decoding has been finished.
    primary := T!.tree[TR_PRIMARY];
    trlast := T!.tree[TR_TREELAST];
    if trlast <= primary then
        # if yes, delete the tree ...
        Unbind( T!.tree );
        # ... and reinitialize the tracing of generator images if
        # it had been initialized before.
        if IsBound( T!.preImagesNewGens ) then
            TzInitGeneratorImages( T );
            if TzOptions(T).printLevel > 0 then
                Print( "#I  Warning: ",
                "the generator images have been reinitialized\n" );
            fi;
        fi;
    else
        # if not, display a serious warning.
        Print( "\n", "#I  **********  WARNING:  the tree decoding is",
            " incomplete !  **********\n\n",
            "#I  hence the isomporphism type of the presented group may",
            " have changed,\n",
            "#I  you should continue by first calling the `DecodeTree'",
            " command again,\n",
            "#I  possibly after changing the Tietze option parameters",
            " appropriately\n\n" );
    fi;

    TzOptions(T).protected := protected;
end );

#############################################################################
##
#M  FpGroupPresentation( <Tietze record> ) . . . .  converts the given Tietze
#M                                         presentation to a fin. pres. group
##
##  `FpGroupPresentation'  constructs the group  defined by the  given Tietze
##  presentation and returns the group record.
##
InstallGlobalFunction( FpGroupPresentation, function (arg)

local P,F, fgens, freegens, frels, G, gens, names, numgens, origin,
      redunds, rels, T, tietze, tzword;

    P:=arg[1];

    if TzOptions(P).printLevel >= 3 then
        Print( "#I  converting the Tietze presentation to a group\n" );
    fi;

    # check the given argument to be a Tietze record.
    TzCheckRecord( P );

    # do not change the given presentation, so work on a copy.
    T := ShallowCopy( P );

    # get some local variables.
    tietze := T!.tietze;
    gens := tietze[TZ_GENERATORS];
    numgens := tietze[TZ_NUMGENS];
    rels := tietze[TZ_RELATORS];
    redunds := tietze[TZ_NUMREDUNDS];

    # tidy up the Tietze presentation.
    if redunds > 0 then  TzRemoveGenerators( T );  fi;
    TzSort( T );

    # create an appropriate free group.
    freegens := tietze[TZ_FREEGENS];
    names := List( gens, g ->
        FamilyObj( gens[1] )!.names[Position( freegens, g )] );

    if Length(arg)>1 then
      F:=FreeGroup(Length(names),arg[2]);
    else
      F := FreeGroup( names );
    fi;

    fgens := GeneratorsOfGroup( F );

    # convert the relators from Tietze words to words in the generators of F.
    frels := [ ];
    for tzword in rels do
        if tzword <> [ ] then
            Add( frels, AbstractWordTietzeWord( tzword, fgens ) );
        fi;
    od;

    # get the resulting finitely presented group.
    G := F / frels;

    # save the generator images, if available.
    origin := rec( );
    if IsBound( T!.imagesOldGens ) then
        origin!.imagesOldGens := Immutable( T!.imagesOldGens );
        origin!.preImagesNewGens := Immutable( T!.preImagesNewGens );
    fi;
    SetTietzeOrigin( G, origin );

    return G;
end );

#############################################################################
##
#M  PresentationFpGroup( <G> [,<print level>] ) . . .  create a Tietze record
##
##  `PresentationFpGroup'  creates a presentation, i.e. a  Tietze record, for
##   the given finitely presented group.
##
InstallGlobalFunction( PresentationFpGroup, function ( arg )

    local F, G, fggens, freegens, frels, gens, grels, i, invs, lengths,
          numgens, numrels, printlevel, rels, T, tietze, total;

    # check the first argument to be a finitely presented group.
    G := arg[1];
    if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
        Error( "<G> must be a finitely presented group" );
    fi;

    # check the second argument to be an integer.
    printlevel := 1;
    if Length( arg ) = 2 then  printlevel := arg[2];  fi;
    if not IsInt( printlevel ) then
        Error( "second argument must be an integer" );
    fi;

    # Create the Presentation.
    T := Objectify( NewType( PresentationsFamily,
                                 IsPresentationDefaultRep
                             and IsPresentation
                             and IsMutable ),
                    rec() );
    tietze := ListWithIdenticalEntries( TZ_LENGTHTIETZE, 0 );
    tietze[TZ_OCCUR]:=false;
    T!.tietze := tietze;

    # initialize the Tietze stack.
    fggens := FreeGeneratorsOfFpGroup( G );
    grels := RelatorsOfFpGroup( G );
    F := FreeGroup( IsLetterWordsFamily,infinity, "_x",
        ElementsFamily( FamilyObj( FreeGroupOfFpGroup( G ) ) )!.names );
    freegens := GeneratorsOfGroup( F );
    tietze[TZ_FREEGENS] := freegens;
    numgens := Length( fggens );
    tietze[TZ_NUMGENS] := numgens;
    gens := List( [ 1 .. numgens ], i -> freegens[i] );
    tietze[TZ_GENERATORS] := gens;
    invs := ShallowCopy( numgens - [ 0 .. 2 * numgens ] );
    tietze[TZ_INVERSES] := invs;
    frels := List( grels, rel -> MappedWord( rel, fggens, gens ) );
    numrels := Length( frels );
    rels := List( [ 1 .. numrels ], i -> TzRelator( T, frels[i] ) );
    lengths := List( [ 1 .. numrels ], i -> Length( rels[i] ) );
    total := Sum( lengths );
    tietze[TZ_NUMRELS] := numrels;
    tietze[TZ_RELATORS] := rels;
    tietze[TZ_LENGTHS] := lengths;
    tietze[TZ_FLAGS] := ListWithIdenticalEntries( numrels, 1 );
    tietze[TZ_TOTAL] := total;
    tietze[TZ_STATUS] := [ 0, 0, -1 ];
    tietze[TZ_MODIFIED] := false;
    T!.generators := tietze[TZ_GENERATORS];
    T!.components := [ 1 .. numgens ];
    for i in [ 1 .. numgens ] do
        T!.(String( i )) := gens[i];
    od;
    T!.nextFree := numgens + 1;
    SetOne(T,Identity( F ));
    T!.identity:=Identity( F );

    # since T is mutable, we must set this attribute "manually"
    SetTzOptions(T,TzOptions(T));

    # initialize some Tietze options
    TzOptions(T).protected := 0;
    TzOptions(T).printLevel:=printlevel;

    # print the status line.
    if TzOptions(T).printLevel >= 2 then  TzPrintStatus( T, true );  fi;

    # return the Tietze record.
    return T;
end );

#############################################################################
##
#M  PrintObj( <T> ) . . . . . . . . . . .  pretty print a presentation record
##
InstallMethod( PrintObj,
    "for a presentation in default representation",
    true,
    [ IsPresentation and IsPresentationDefaultRep ], 0,
    function( T )

    local numgens, numrels, tietze, total;

    # get number of generators, number of relators, and total length.
    tietze := T!.tietze;
    numgens := tietze[TZ_NUMGENS] - tietze[TZ_NUMREDUNDS];
    numrels := tietze[TZ_NUMRELS];
    total := tietze[TZ_TOTAL];

    # print the Tietze status line.
    Print( "<presentation with ", numgens, " gens and ", numrels,
        " rels of total length ", total, ">" );

end );

#############################################################################
##
#M  ShallowCopy( <T> )
##
InstallMethod( ShallowCopy,
    "for a presentation in default representation", true,
    [ IsPresentation and IsPresentationDefaultRep ], 0, StructuralCopy );

#############################################################################
##
#M  PresentationRegularPermutationGroup(<G>)  . . .  construct a presentation
#M                                           from a regular permutation group
##
##  `PresentationRegularPermutationGroup'  constructs a presentation from the
##  given  regular permutation group  using  John Cannon's  relations finding
##  algorithm.
##
InstallGlobalFunction( PresentationRegularPermutationGroup, function ( G )

    # check G to be a regular permutation group.
    if not ( IsPermGroup( G ) and IsRegular( G ) ) then
        Error( "the given group must be a regular permutation group" );
    fi;
    return PresentationRegularPermutationGroupNC( G );
end );

#############################################################################
##
#M  PresentationRegularPermutationGroupNC(<G>)  . .  construct a presentation
#M                                           from a regular permutation group
##
##  `PresentationRegularPermutationGroupNC' constructs a presentation from
##  the given regular permutation group using John Cannon's relations finding
##  algorithm.
##
##  In this NC version it is assumed, but not checked that G is a regular
##  permutation group.
##
InstallGlobalFunction( PresentationRegularPermutationGroupNC, function ( G )
    local   cosets,       # right cosets of G by its trivial subgroup H
            F,            # given free group
            P,            # presentation to be consructed
            ng1,          # position number of identity element in G
            idword,       # identity element of F
            table,        # columns in the table for gens
            rels,         # representatives of the relators
            relsGen,      # relators sorted by start generator
            subgroup,     # rows for the subgroup gens
            i, j,         # loop variables
            gen,          # loop variables for generator
            gen0, inv0,   # loop variables for generator cols
            g, g1,        # loop variables for generator cols
            c,            # loop variable for coset
            rel,          # loop variables for relator
            rels1,        # list of relators
            app,          # arguments list for `MakeConsequences'
            index,        # index of the table
            col,          # generator col in auxiliary table
            perm,         # variable for permutations
            fgens,        # generators of F
            gens2,        # the above abstract gens and their inverses
            perms,        # permutation generators of G
            moved,        # list of points on which G acts,
            ngens,        # number of generators of G
            ngens2,       # twice the above number
            order,        # order of a generator
            actcos,       # part 1 of Schreier vector of G by H
            actgen,       # part 2 of Schreier vector of G by H
            tab0,         # auxiliary table in parallel to table <table>
            cosRange,     # range from 1 to index (= number of cosets)
            genRange,     # range of the odd integers from 1 to 2*ngens-1
            geners,       # order in which the table cols are worked off
            next;         # local coset number;

    # initialize some local variables.
    perms := GeneratorsOfGroup( G );
    ngens := Length( perms );
    ngens2 := ngens * 2;
    ng1 := 1;
    index := NrMovedPoints( perms );
    tab0 := [];
    table := [];
    subgroup := [];
    cosRange := [ 1 .. index ];
    genRange := List( [ 1 .. ngens ], i -> 2*i-1 );
    rels := [];
    F := FreeGroup( ngens );
    fgens := GeneratorsOfGroup( F );
    gens2 := [];
    idword := One( fgens[1] );

    # ensure that the permutations act on the points 1 to index (note that
    # index is the degree of G).
    if LargestMovedPoint( perms ) > index then
        moved := MovedPoints( perms );
        perm := MappingPermListList( moved, [ 1 .. index ] );
        perms := OnTuples( perms, perm );
    fi;

    # get a coset table from the permutations,
    # and introduce appropriate relators for the involutory generators
    for i in [ 1 .. ngens ] do
        Add( gens2, fgens[i] );
        Add( gens2, fgens[i]^-1 );
        perm := perms[i];
        col := OnTuples( cosRange, perm );
        gen := ListWithIdenticalEntries( index, 0 );
        Add( tab0, col );
        Add( table, gen );
        order := Order( perms[i] );
        if order = 2 then
            Add( rels, fgens[i]^2 );
        else
            col := OnTuples( cosRange, perm^-1 );
            gen := ListWithIdenticalEntries( index, 0 );
        fi;
        Add( tab0, col );
        Add( table, gen );
    od;

    # define an appropriate ordering of the cosets,
    # enter the definitions in the table,
    # and construct the Schreier vector,
    cosets := ListWithIdenticalEntries( index, 0 );
    actcos := ListWithIdenticalEntries( index, 0 );
    actgen := ListWithIdenticalEntries( index, 0 );
    cosets[1] := ng1;
    actcos[ng1] := ng1;
    j := 1;
    i := 0;
    while i < index do
        i := i + 1;
        c := cosets[i];
        g := 0;
        while g < ngens2 do
            g := g + 1;
            next := tab0[g][c];
            if next > 0 and actcos[next] = 0 then
                g1 := g + 2*(g mod 2) - 1;
                table[g][c] := next;
                table[g1][next] := c;
                tab0[g][c] := 0;
                tab0[g1][next] := 0;
                actcos[next] := c;
                actgen[next] := g;
                j := j + 1;
                cosets[j] := next;
                if j = index then
                    g := ngens2;
                    i := index;
                fi;
            fi;
        od;
    od;

    # compute the representatives for the relators
    rels := RelatorRepresentatives( rels );

    # make the structure that is passed to `MakeConsequences'
    app := ListWithIdenticalEntries( 12, 0 );

    # note: we have, in particular, set app[12] to zero as we do not want
    # minimal gaps to be marked in the coset table

    app[1] := table;
    app[5] := subgroup;

    # run through the coset table and find the next undefined entry
    geners := [ 1 .. ngens2 ];
    for i in cosets do
        for j in geners do
            if table[j][i] <= 0 then

                # define the entry appropriately,
                g := j + 2*(j mod 2) - 1;
                c := tab0[j][i];
                table[j][i] := c;
                table[g][c] := i;
                tab0[j][i] := 0;
                tab0[g][c] := 0;

                # construct the associated relator
                rel := idword;
                while c <> ng1 do
                    g := actgen[c];
                    rel := rel * gens2[g]^-1;
                    c := actcos[c];
                od;
                rel := rel^-1 * gens2[j]^-1;
                c := i;
                while c <> ng1 do
                    g := actgen[c];
                    rel := rel * gens2[g]^-1;
                    c := actcos[c];
                od;

                # compute its representative,
                # and add it to the set of relators
                rels1 := RelatorRepresentatives( [ rel ] );
                if Length( rels1 ) > 0 then
                    rel := rels1[1];
                    if not rel in rels then
                        Add( rels, rel );
                    fi;
                fi;

                # make the rows for the relators and distribute over relsGen
                relsGen := RelsSortedByStartGen( fgens, rels, table, true );
                app[4] := relsGen;

                # mark all already defined entries of table by a zero in
                # tab0
                for g in genRange do
                    gen := table[g];
                    gen0 := tab0[g];
                    inv0 := tab0[g+1];
                    for c in cosRange do
                        if gen[c] > 0 then
                            gen0[c] := 0;
                            inv0[gen[c]] := 0;
                        fi;
                    od;
                od;

                # continue the enumeration and find all consequences
                for g in genRange do
                    gen0 := tab0[g];
                    for c in cosRange do
                        if gen0[c] = 0 then
                            app[10] := g;
                            app[11] := c;
                            MakeConsequences( app );
                        fi;
                    od;
                od;
            fi;
        od;
    od;

    # construct a finitely presented group from the relations,
    # add the Schreier vector to its components, and return it
    P := PresentationFpGroup( F / rels, 0 );
    TzOptions(P).protected := ngens;
    TzGoGo( P );
    TzOptions(P).protected := 0;
    TzOptions(P).printLevel := 1;

    # return the resulting presentation
    return P;
end );

#############################################################################
##
#M  PresentationViaCosetTable(<G>)  . . . . . . . .  construct a presentation
#M  PresentationViaCosetTable(<G>,<F>,<words>) . . . . .  for the given group
##
##  `PresentationViaCosetTable'   constructs   a  presentation  for  a  given
##  concrete  group.  It applies  John  Cannon's  relations finding algorithm
##  which has been described in
##
##    John J. Cannon:  Construction of  defining relators  for  finte groups.
##    Discrete Math. 5 (1973), 105-129, and in
##
##    Joachim Neubueser: An elementary introduction to coset table methods in
##    computational  group theory.  Groups-St Andrews 1981,  edited by C. M.
##    Campbell and E. F. Robertson, pp. 1-45.  London Math. Soc. Lecture Note
##    Series no. 71, Cambridge Univ. Press, Cambridge, 1982.
##
##  If only a group  <G>  has been  specified,  the single stage algorithm is
##  applied.
##
##  If the  two stage algorithm  is to  be used,  `PresentationViaCosetTable'
##  expects a subgroup <H> of <G> to be described by two additional arguments
##  <F>  and  <words>,  where  <F>  is a  free group  with the same number of
##  generators as  <G>,  and  <words> is a list of words in the generators of
##  <F>  which supply  a list of generators of  <H>  if they are evaluated as
##  words in the corresponding generators of <G>.
##
InstallGlobalFunction( PresentationViaCosetTable, function ( arg )
    local   G,          # given group
            F,          # given or constructed free group
            fgens,      # generators of F
            words,      # words (in the generators of F) defing H
            twords,     # tidied up list of words
            H,          # subgroup
            elts,       # elements of G or H
            cosets,     # right cosets of G with respect to H
            R1,         # record containing an fp group isomorphic to H
            R2,         # record containing an fp group isomorphic to G
            P,          # resulting presentation
            ggens,      # concrete generators of G
            hgens,      # concrete generators of H
            thgens,     # tidied up list of generators of H
            ngens,      # number of generators of G
            one,        # identity element of G
            F1,         # free group with same number of generators as H
            FP2,        # fp group isomorphic to G
            i;          # loop variable

    # check the first argument to be a group
    G := arg[1];
    if not IsGroup( G ) then
        Error( "first argument must be a group" );
    fi;
    ggens := GeneratorsOfGroup( G );
    ngens := Length( ggens );

    # check if a subgroup has been specified
    if Length( arg ) = 1 then

        # apply the single stage algorithm
        Info( InfoFpGroup, 1,
            "calling the single stage relations finding algorithm" );

        # use a special method for regular permutation groups
        if IsPermGroup( G ) then
            # compute the size of G to speed up the regularity check
            Size( G );
            if IsRegular( G ) then
                return PresentationRegularPermutationGroupNC( G );
            fi;
        fi;

        # construct a presentation for G
        elts := AsSSortedList( G );
        F := FreeGroup( ngens );
        R2 := RelsViaCosetTable( G, elts, F );

    else

        # check the second argument to be an fp group.
        F := arg[2];
        if not IsFreeGroup( F ) then
            Error( "second argument must be a free group" );
        fi;

        # check F for having the same number of generators as G
        fgens := GeneratorsOfGroup( F );
        if Length( fgens ) <> ngens then
            Error( "the given groups have different number of generators" );
        fi;

        # get the subgroup H
        words := arg[3];
        hgens := List( words, w -> MappedWord( w, fgens, ggens ) );
        H := Subgroup( G, hgens );

        if Size( H ) = 1 or Size( H ) = Size( G ) then

            # apply the single stage algorithm
            Info( InfoFpGroup, 1,
                "calling the single stage relations finding algorithm" );
            elts := AsSSortedList( G );
            R2 := RelsViaCosetTable( G, elts, F );

        else

            # apply the two stage algorithm
            Info( InfoFpGroup, 1,
                "calling the two stage relations finding algorithm" );
            Info( InfoFpGroup, 1,
                "using a subgroup of size ", Size( H ), " and index ",
                Size( G ) / Size( H ) );
            # eliminate words which define the identity of G
            one := One( ggens[1] );
            thgens := [];
            twords := [];
            for i in [ 1 .. Length( hgens ) ] do
                if hgens[i] <> one and not hgens[i] in thgens
                    and not hgens[i]^-1 in thgens then
                    Add( thgens, hgens[i] );
                    Add( twords, words[i] );
                fi;
            od;
            hgens := thgens;
            words := twords;

            # construct a presentation for the subgroup H
            elts := AsSSortedList( H );
            F1 := FreeGroup( Length( hgens ) );
            R1 := RelsViaCosetTable( H, elts, F1, hgens );

            # construct a presentation for the group G
            cosets := RightCosets( G, H );
            R2 := RelsViaCosetTable( G, cosets, F, words, H, R1 );

        fi;
    fi;

    # simplify the resulting presentation by Tietze transformations,
    # but do not eliminate any generators
    FP2 := R2.fpGroup;
    P := PresentationFpGroup( FP2, 0 );
    TzOptions(P).protected := ngens;
    TzGoGo( P );
    TzOptions(P).protected := 0;
    TzOptions(P).printLevel := 1;

    # return the resulting presentation
    return P;
end );

#############################################################################
##
#M  RelsViaCosetTable(<G>,<cosets>,<F>)  . . . . . construct relators for the
#M  RelsViaCosetTable(<G>,<cosets>,<F>,<ggens>)  . . . . . . . given concrete
#M  RelsViaCosetTable(<G>,<cosets>,<F>,<words>,<H>,<R1>)  . . . . . . . group
##
##  `RelsViaCosetTable'  constructs a defining set of relators  for the given
##  concrete group using John Cannon's relations finding algorithm.
##
##  It is a  subroutine  of function  `PresentationViaCosetTable'.  Hence its
##  input and output are specifically designed only for this purpose,  and it
##  does not check the arguments.
##

InstallGlobalFunction( RelsViaCosetTable, function ( arg )
    local   G,            # given group
            cosets,       # right cosets of G with respect to H
            F,            # given free group
            words,        # given words for the generators of H
            H,            # subgroup, if specified
            F1,           # free group associated to H
            R1,           # record containing an fp group isomorphic to H
            R2,           # record containing an fp group isomorphic to G
            FP1,          # fp group isomorphic to H
            fhgens,       # generators of F1
            hrels,        # relators of F1
            helts,        # list of elements of H
            ng1,          # position number of identity element in G
            nh1,          # position number of identity element in H
            idword,       # identity element of F
            perms,        # permutations induced by the gens on the cosets
            stage,        # 1 or 2
            table,        # columns in the table for gens
            rels,         # representatives of the relators
            relsGen,      # relators sorted by start generator
            subgroup,     # rows for the subgroup gens
            i, j,         # loop variables
            gen,          # loop variables for generator
            gen0, inv0,   # loop variables for generator cols
            g, g1,        # loop variables for generator cols
            c,            # loop variable for coset
            rel,          # loop variables for relator
            rels1,        # list of relators
            app,          # arguments list for `MakeConsequences'
            index,        # index of the table
            col,          # generator col in auxiliary table
            perm,         # permutations induced by a generator on the cosets
            fgens,        # generators of F
            gens2,        # the above abstract gens and their inverses
            ggens,        # concrete generators of G
            ngens,        # number of generators of G
            ngens2,       # twice the above number
            order,        # order of a generator
            actcos,       # part 1 of Schreier vector of G by H
            actgen,       # part 2 of Schreier vector of G by H
            tab0,         # auxiliary table in parallel to table <table>
            cosRange,     # range from 1 to index (= number of cosets)
            genRange,     # range of the odd integers from 1 to 2*ngens-1
            geners,       # order in which the table cols are worked off
            next,         # local coset number
            left1,        # part 1 of Schreier vector of H by trivial group
            right1,       # part 2 of Schreier vector of H by trivial group
            n,            # number of subgroup element
            words2,       # words for the generators of H and their inverses
            h;            # subgroup element

    # get the arguments, and initialize some local variables

    G := arg[1];
    cosets := arg[2];
    F := arg[3];
    if Length( arg ) = 4 then
        ggens := arg[4];
    else
        ggens := GeneratorsOfGroup( G );
    fi;
    ngens := Length( ggens );
    ngens2 := ngens * 2;
    if cosets[1] in G then
        ng1 := PositionSorted( cosets, cosets[1]^0 );
    else
        ng1 := 1;
    fi;
    index := Length( cosets );
    tab0 := [];
    table := [];
    subgroup := [];
    cosRange := [ 1 .. index ];
    genRange := List( [ 1 .. ngens ], i -> 2*i-1 );

    if Length( arg ) < 5 then
        stage := 1;
        rels := [];
    else
        stage := 2;
        words := arg[4];
        H := arg[5];
        helts := AsSSortedList( H );
        nh1 := PositionSorted( helts, helts[1]^0 );
        R1 := arg[6];
        FP1 := R1.fpGroup;
        F1 := FreeGroupOfFpGroup( FP1 );
        fhgens := GeneratorsOfGroup( F1 );
        hrels := RelatorsOfFpGroup( FP1 );
        # initialize the relators of F2 by the rewritten relators of F1
        rels := List( hrels, rel -> MappedWord( rel, fhgens, words ) );
        # get the Schreier vector for the elements of H
        left1 := R1.actcos;
        right1 := R1.actgen;
        # extend the list of the generators of F1 as words in the abstract
        # generators of F2 by their inverses
        words2 := [];
        for i in [ 1 .. Length( words ) ] do
            Add( words2, words[i] );
            Add( words2, words[i]^-1 );
        od;
    fi;

    fgens := GeneratorsOfGroup( F );
    gens2 := [];
    idword := One( fgens[1] );

    # get the permutations induced by the generators of G on the given
    # cosets
    perms := List( ggens, gen -> Permutation( gen, cosets, OnRight ) );

    # get a coset table from the permutations,
    # and introduce appropriate relators for the involutory generators
    for i in [ 1 .. ngens ] do
        Add( gens2, fgens[i] );
        Add( gens2, fgens[i]^-1 );
        perm := perms[i];
        col := OnTuples( cosRange, perm );
        gen := ListWithIdenticalEntries( index, 0 );
        Add( tab0, col );
        Add( table, gen );
        order := Order( ggens[i] );
        if order = 2 then
            Add( rels, fgens[i]^2 );
        else
            col := OnTuples( cosRange, perm^-1 );
            gen := ListWithIdenticalEntries( index, 0 );
        fi;
        Add( tab0, col );
        Add( table, gen );
    od;

    # define an appropriate ordering of the cosets,
    # enter the definitions in the table,
    # and construct the Schreier vector,
    cosets := ListWithIdenticalEntries( index, 0 );
    actcos := ListWithIdenticalEntries( index, 0 );
    actgen := ListWithIdenticalEntries( index, 0 );
    cosets[1] := ng1;
    actcos[ng1] := ng1;
    j := 1;
    i := 0;
    while i < index do
        i := i + 1;
        c := cosets[i];
        g := 0;
        while g < ngens2 do
            g := g + 1;
            next := tab0[g][c];
            if next > 0 and actcos[next] = 0 then
                g1 := g + 2*(g mod 2) - 1;
                table[g][c] := next;
                table[g1][next] := c;
                tab0[g][c] := 0;
                tab0[g1][next] := 0;
                actcos[next] := c;
                actgen[next] := g;
                j := j + 1;
                cosets[j] := next;
                if j = index then
                    g := ngens2;
                    i := index;
                fi;
            fi;
        od;
    od;

    # compute the representatives for the relators
    rels := RelatorRepresentatives( rels );

    # make the structure that is passed to `MakeConsequences'
    app := ListWithIdenticalEntries( 12, 0 );

    # note: we have, in particular, set app[12] to zero as we do not want
    # minimal gaps to be marked in the coset table

    app[1] := table;
    app[5] := subgroup;

    # in case stage = 2 we have to handle subgroup relators
    if stage = 2 then

        # make the rows for the relators and distribute over relsGen
        relsGen := RelsSortedByStartGen( fgens, rels, table, true );
        app[4] := relsGen;

        # start the enumeration and find all consequences
        for g in genRange do
            gen0 := tab0[g];
            for c in cosRange do
                if gen0[c] = 0 then
                    app[10] := g;
                    app[11] := c;
                    n := MakeConsequences( app );
                fi;
            od;
        od;
    fi;

    # run through the coset table and find the next undefined entry
    geners := [ 1 .. ngens2 ];
    for i in cosets do
        for j in geners do
            if table[j][i] <= 0 then

                # define the entry appropriately,
                g := j + 2*(j mod 2) - 1;
                c := tab0[j][i];
                table[j][i] := c;
                table[g][c] := i;
                tab0[j][i] := 0;
                tab0[g][c] := 0;

                # construct the associated relator
                rel := idword;
                while c <> ng1 do
                    g := actgen[c];
                    rel := rel * gens2[g]^-1;
                    c := actcos[c];
                od;
                rel := rel^-1 * gens2[j]^-1;
                c := i;
                while c <> ng1 do
                    g := actgen[c];
                    rel := rel * gens2[g]^-1;
                    c := actcos[c];
                od;
                if stage = 2 then
                    h := MappedWord( rel, fgens, ggens );
                    n := PositionSorted( helts, h );
                    while n <> nh1 do
                        g := right1[n];
                        rel := rel * words2[g]^-1;
                        n := left1[n];
                    od;
                fi;

                # compute its representative,
                # and add it to the set of relators
                rels1 := RelatorRepresentatives( [ rel ] );
                if Length( rels1 ) > 0 then
                    rel := rels1[1];
                    if not rel in rels then
                        Add( rels, rel );
                    fi;
                fi;

                # make the rows for the relators and distribute over relsGen
                relsGen := RelsSortedByStartGen( fgens, rels, table, true );
                app[4] := relsGen;

                # mark all already defined entries of table by a zero in
                # tab0
                for g in genRange do
                    gen := table[g];
                    gen0 := tab0[g];
                    inv0 := tab0[g+1];
                    for c in cosRange do
                        if gen[c] > 0 then
                            gen0[c] := 0;
                            inv0[gen[c]] := 0;
                        fi;
                    od;
                od;

                # continue the enumeration and find all consequences
                for g in genRange do
                    gen0 := tab0[g];
                    for c in cosRange do
                        if gen0[c] = 0 then
                            app[10] := g;
                            app[11] := c;
                            n := MakeConsequences( app );
                        fi;
                    od;
                od;
            fi;
        od;
    od;

    # construct a finitely presented group from the relations,
    # add the Schreier vector to its components, and return it
    R2 := rec( );
    R2.fpGroup := F / rels;
    R2.actcos := actcos;
    R2.actgen := actgen;
    return R2;
end );

#############################################################################
##
#M  RemoveRelator( <Tietze record>, <n> ) . . . . . . . . .  remove a relator
#M                                                        from a presentation
##
##  removes the <n>-th relator from the given Tietze presentation.
##
InstallGlobalFunction( RemoveRelator, function ( T, n )

    local invs, leng, lengths, num, numgens1, numrels, rels, tietze;

    # check the first argument to be a Tietze record.
    TzCheckRecord( T );

    # get some local variables.
    tietze := T!.tietze;
    rels := tietze[TZ_RELATORS];
    numrels := tietze[TZ_NUMRELS];
    lengths := tietze[TZ_LENGTHS];
    invs := tietze[TZ_INVERSES];
    numgens1 := tietze[TZ_NUMGENS] + 1;

    # check the second argument to be in range.
    if ( n < 1 or n > numrels ) then
        Error( "relator number out of range" );
    fi;

    # print a message.
    if TzOptions(T).printLevel >= 3 then
        Print( "#I  removing the ", n, "th relator\n" );
    fi;

    # check if the nth relator has defined an involution.
    leng := lengths[n];
    if leng = 2 and rels[n][1] = rels[n][2] then
        num := rels[n][1];
        if num < 0 then  num := -num;  fi;
        if invs[numgens1+num] = num then  invs[numgens1+num] := -num;  fi;
    fi;

    # remove the nth relator, and make the Tietze lists consistent.
    rels[n] := [ ];
    lengths[n] := 0;
    tietze[TZ_TOTAL] := tietze[TZ_TOTAL] - leng;
    TzSort( T );
    if TzOptions(T).printLevel >= 2 then  TzPrintStatus( T, true );  fi;
end );

#############################################################################
##
#M  AbstractWordTietzeWord( <word>, <fgens> )  . . . .  convert a Tietze word
#M                                                        to an abstract word
##
InstallGlobalFunction( AbstractWordTietzeWord,
function(w,gens)
  return AssocWordByLetterRep(FamilyObj(gens[1]),w,gens);
end);

#############################################################################
##
#M  TzCheckRecord( <Tietze record> )  . . . .  check Tietze record components
##
##  `TzCheckRecord'  checks some components of the  given Tietze record to be
##  consistent.
##
InstallGlobalFunction( TzCheckRecord, function ( T )

    local tietze;

    # check the given argument to be a Presentation.
    if not IsPresentation( T ) then
        Error( "argument must be a Presentation" );
    fi;

    # check the generator lists to be consistent.
    tietze := T!.tietze;
    if not ( IsIdenticalObj( T!.generators, tietze[TZ_GENERATORS] ) ) or
        Length( tietze[TZ_GENERATORS] ) <> tietze[TZ_NUMGENS] then
        Error( "inconsistent generator lists" );
    fi;

    # check the inverses list.
    if Length( tietze[TZ_INVERSES] ) <> 2 * tietze[TZ_NUMGENS] + 1 then
        Error( "inconsistent generator inverses" );
    fi;

    # check the relator list.
    if Length( tietze[TZ_RELATORS] ) <> tietze[TZ_NUMRELS] or
        Length( tietze[TZ_LENGTHS] ) <> tietze[TZ_NUMRELS] or
        Length( tietze[TZ_FLAGS] ) <> tietze[TZ_NUMRELS] then
        Error( "inconsistent relators" );
    fi;

end );

#############################################################################
##
#M  TzEliminate( <Tietze record> ) . . . . . . . . . . eliminates a generator
#M  TzEliminate( <Tietze record>, <gen> )  . . . . . eliminates generator gen
#M  TzEliminate( <Tietze record>, <n> ) . . . . . . . eliminates n generators
##
##  If a generator has been specified,  then  `TzEliminate'  eliminates it if
##  possible, i. e. if it can be isolated in some appropriate relator.  If no
##  generator  has  been  specified ,   then  `TzEliminate'  eliminates  some
##  appropriate  generator  if possible  and if the resulting total length of
##  the relators will not exceed  the parameter  TzOptions(T).lengthLimit  or
##  the value 2^31-1.
##
InstallGlobalFunction( TzEliminate, function ( arg )

    local eliminations, gennum, n, numgens, numgenslimit, T, tietze;

    # check the number of arguments.
    if Length( arg ) > 2 or Length( arg ) < 1 then
        Error( "usage: TzEliminate( <Tietze record> [, <generator> ] )" );
    fi;

    # check the first argument to be a Tietze record.
    T := arg[1];
    TzCheckRecord( T );
    TzTestInitialSetup(T); # run `1Or2Relators' if not yet done
    tietze := T!.tietze;

    # get the arguments.
    gennum := 0;
    n := 1;
    if Length( arg ) = 2 then
        if IsInt( arg[2] ) then
            n := arg[2];
        else
            gennum := Position( tietze[TZ_GENERATORS], arg[2] );
            if gennum = fail then  Error(
                "usage: TzEliminate( <Tietze record> [, <generator> ] )" );
            fi;
        fi;
    fi;

    if n = 1 then

        # call the appropriate routine to eliminate one generator.
        if gennum = 0 then  TzEliminateGen1( T );
        else  TzEliminateGen( T, gennum );  fi;
        if tietze[TZ_NUMREDUNDS] > 0 then  TzRemoveGenerators( T );  fi;

        # handle relators of length 1 or 2.
        TzHandleLength1Or2Relators( T );

        # sort the relators and print the status line.
        TzSort( T );
        if TzOptions(T).printLevel >= 1 then  TzPrintStatus( T, true );  fi;

    else

        # eliminate n generators.
        numgens := tietze[TZ_NUMGENS];
        eliminations := TzOptions(T).eliminationsLimit;
        numgenslimit := TzOptions(T).generatorsLimit;
        TzOptions(T).eliminationsLimit := n;
        TzOptions(T).generatorsLimit := numgens - n;
        TzEliminateGens( T );
        TzOptions(T).eliminationsLimit := eliminations;
        TzOptions(T).generatorsLimit := numgenslimit;
    fi;
end );

# eliminate generators by removing first those that occur rarely, up to
# frequency lim
BindGlobal("TzEliminateRareOcurrences",function(pres,lim)
local prepare,gens,rels,sel,cnt,i,alde,freq;
  prepare:=function()
  local r,j,idx;
    gens:=List(pres!.generators,x->LetterRepAssocWord(x)[1]);
    rels:=pres!.tietze[TZ_RELATORS];
    cnt:=List([1..Maximum(gens)],x->0);
    for r in rels do
      for j in r do
        j:=AbsInt(j);
        cnt[j]:=cnt[j]+1;
      od;
    od;
    sel:=[];

    repeat
      idx:=Filtered([1..Length(cnt)],x->cnt[x]>0 and cnt[x]<=freq);
      idx:=Difference(idx,alde);
      idx:=Difference(idx,sel);
      sel:=Concatenation(sel,idx);
      if Length(sel)<20 and freq<lim then
        freq:=freq+1;
      fi;
    until Length(sel)>=20 or freq=lim;

    alde:=Union(alde,sel);
  end;

  alde:=[];
  TzSearch(pres);
  if Length(pres!.generators)=0 then return alde;fi;
  freq:=1;
  prepare();
  while Length(sel)>0 do
    sel:=pres!.generators{sel};
    for i in sel do
      #Print("elim ",i,"\n");
      TzEliminateGen(pres,Position(pres!.generators,i));
    od;
    TzHandleLength1Or2Relators(pres);
    TzSearchEqual(pres);
    TzFindCyclicJoins(pres);
    TzSearch(pres);
    if Length(pres!.generators)=0 then return alde;fi;
    prepare();
  od;
  return alde;
end);

#############################################################################
##
#M  TzEliminateFromTree( <Tietze record> ) . .  eliminates the last generator
#M                                                              from the tree
##
##  `TzEliminateFromTree'  eliminates  the  last  Tietze  generator.  If that
##  generator cannot be isolated in any Tietze relator,  then its  definition
##  is  taken  from  the tree  and added  as an  additional  Tietze  relator,
##  extending  the  set  of  Tietze generators  appropriately,  if necessary.
##  However,  the elimination  will not be  performed  if the resulting total
##  length of the relators  cannot be guaranteed  to not exceed the parameter
##  TzOptions(T).lengthLimit or the value 2^31-1.
##
InstallGlobalFunction( TzEliminateFromTree, function ( T )

    local exp, factor, flags, gen, gens, i, invnum, invs, leng, length,
          lengths, num, numgens, numrels, occRelNum, occur, occTotal, pair,
          pair1, pointers, pos, primary, ptr, rel, rels, space,
          spacelimit, tietze, tree, treelength, treeNums, trlast, word;

    # check the first argument to be a Presentation.
    if not IsPresentation( T ) then
        Error( "argument must be a Presentation" );
    fi;
    TzTestInitialSetup(T); # run `1Or2Relators' if not yet done

    # get some local variables.
    tietze := T!.tietze;
    gens := tietze[TZ_GENERATORS];
    numgens := tietze[TZ_NUMGENS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    numrels := tietze[TZ_NUMRELS];
    flags := tietze[TZ_FLAGS];
    lengths := tietze[TZ_LENGTHS];

    # get some more local variables.
    tree := T!.tree;
    treelength := tree[TR_TREELENGTH];
    primary := tree[TR_PRIMARY];
    trlast := tree[TR_TREELAST];
    treeNums := tree[TR_TREENUMS];
    pointers := tree[TR_TREEPOINTERS];

    spacelimit := Minimum( TzOptions(T).lengthLimit, 2^31 - 1 );
    tietze[TZ_MODIFIED] := false;
    occTotal := 0;

    # get the number of the last occurring generator.
    while occTotal = 0 do

        # get the number of the last generator.
        while trlast > primary and pointers[trlast] <= treelength do
            trlast := trlast - 1;
        od;
        tree[TR_TREELAST] := trlast;
        if trlast <= primary then  return;  fi;

        # determine the number of occurrences of the last generator.
        num := pointers[trlast] - treelength;
        occur := TzOccurrences( tietze, num );
        occTotal := occur[1][1];

        # if the last generator does not occur in the relators, mark it to
        # be redundant.
        if occTotal = 0 then
            invs[numgens+1-num] := 0;
            tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1;
            trlast := trlast - 1;
        fi;
    od;

    if occur[3][1] > 1 then

        # print a message.
        if TzOptions(T).printLevel >= 2 then
            Print( "#I  adding relator from tree position ", trlast, "\n" );
        fi;

        # get the defining word from the tree.
        pair := [ 0, 0 ];
        for i in [ 1 .. 2 ] do

            exp := 1;
            ptr := tree[i][trlast];
            if ptr < 0 then
                exp := - exp;
                ptr := - ptr;
            fi;

            if pointers[ptr] = ptr then
                # add this tree generator to the list of generators.
                gen := TzNewGenerator( T );
                numgens := tietze[TZ_NUMGENS];
                gens := tietze[TZ_GENERATORS];
                invs := tietze[TZ_INVERSES];
                treeNums[numgens] := ptr;
                pointers[ptr] := treelength + numgens;
                if TzOptions(T).printLevel >= 2 then
                    Print( "#I  adding generator ", gens[numgens],
                    " from tree position ", ptr, "\n" );
                fi;
            else
                # find this tree generator in the list of generators.
                while ptr > 0 and pointers[ptr] <= treelength do
                    ptr := pointers[ptr];
                    if ptr < 0 then
                        exp := - exp;
                        ptr := - ptr;
                    fi;
                od;
            fi;

            # now get the generator number of the current factor.
            if ptr = 0 then
                factor := 0;
            else
                factor := pointers[ptr] - treelength;
                if treeNums[factor] < 0 then  exp := - exp;  fi;
                if exp < 0 then  factor := invs[numgens+1+factor];  fi;
            fi;
            pair[i] := factor;
        od;

        # invert the defining word, if necessary.
        if treeNums[num] < 0 then
            pair1 := pair[1];
            pair[1] := invs[numgens+1+pair[2]];
            pair[2] := invs[numgens+1+pair1];
        fi;

        # add the corresponding relator to the set of relators.
        invnum := invs[numgens+1+num];
        if pair[1] = invs[numgens+1+pair[2]] then
            rel := [ invnum ];  leng := 1;
        elif pair[1] = 0 then
            rel := [ invnum, pair[2] ];  leng := 2;
        elif pair[2] = 0 then
            rel := [ invnum, pair[1] ];  leng := 2;
        else
            rel := [ invnum, pair[1], pair[2] ];  leng := 3;
        fi;
        numrels := numrels + 1;
        rels[numrels] := rel;
        lengths[numrels] := leng;
        flags[numrels] := 1;
        tietze[TZ_NUMRELS] := numrels;
        tietze[TZ_TOTAL] := tietze[TZ_TOTAL] + leng;
        tietze[TZ_MODIFIED] := true;
        tietze[TZ_OCCUR]:=false;

        # if the new relator has length at most 2, handle it by calling the
        # appropriate subroutine, and then return.
        if leng <= 2 then
            TzHandleLength1Or2Relators( T );
            trlast := trlast - 1;
            while trlast > primary and pointers[trlast] <= treelength do
                trlast := trlast - 1;
            od;
            tree[TR_TREELAST] := trlast;
            return;
        fi;

        # else update the number of occurrences of the last generator, and
        # continue.
        occTotal := occTotal + 1;
        occur[1][1] := occTotal;
        occur[2][1] := numrels;
        occur[3][1] := 1;
    fi;

    occRelNum := occur[2][1];

    length := lengths[occRelNum];
    space := (occTotal - 1) * (length - 1) - length;

    if tietze[TZ_TOTAL] + space <= spacelimit then

        # find the substituting word.
        gen := num;
        rel := rels[occRelNum];
        length := lengths[occRelNum];
        pos := Position( rel, gen );
        if pos = fail then
            gen := -gen;
            pos := Position( rel, gen );
        fi;
        word := Concatenation( rel{ [pos+1..length] }, rel{ [1..pos-1] } );

        # replace all occurrences of gen by word^-1.
        if TzOptions(T).printLevel >= 2 then
          Print( "#I  eliminating ", gens[num], " = " );
          if Length(word)>500 then
            Print("<word of length ",Length(word)," >\n");
          elif gen > 0 then
              Print( AbstractWordTietzeWord( word, gens )^-1, "\n");
          else
              Print( AbstractWordTietzeWord( word, gens ), "\n" );
          fi;
        fi;
        TzSubstituteGen( tietze, -gen, word );

        # mark gen to be redundant.
        invs[numgens+1-num] := 0;
        tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1;
        tietze[TZ_MODIFIED] := true;
        tietze[TZ_OCCUR]:=false;
        trlast := trlast - 1;
        while trlast > primary and pointers[trlast] <= treelength do
            trlast := trlast - 1;
        od;
        tree[TR_TREELAST] := trlast;
    elif TzOptions(T).printLevel >= 1 then
        Print( "#I  replacement of generators stopped by length limit\n" );
    fi;
end );

#############################################################################
##
#M  TzEliminateGen( <Tietze record>, <n> ) . . . eliminates the nth generator
##
##  `TzEliminateGen' eliminates the Tietze generator tietze[TZ_GENERATORS][n]
##  if possible, i. e. if that generator can be isolated  in some appropriate
##  Tietze relator.  However,  the elimination  will not be  performed if the
##  resulting total length of the relators cannot be guaranteed to not exceed
##  the parameter TzOptions(T).lengthLimit or the value 2^31-1.
##
InstallGlobalFunction( TzEliminateGen, function ( T, num )

    local gen, gens, invs, length, lengths, numgens, numrels, occRelNum,
          occur, occTotal, pos, rel, rels, space, spacelimit, tietze, word;

    # check the first argument to be a Presentation.
    if not IsPresentation( T ) then
        Error( "argument must be a Presentation" );
    fi;
    TzTestInitialSetup(T); # run `1Or2Relators' if not yet done
    tietze := T!.tietze;
    spacelimit := Minimum( TzOptions(T).lengthLimit, 2^31 - 1 );

    tietze[TZ_MODIFIED] := false;

    gens := tietze[TZ_GENERATORS];
    numgens := tietze[TZ_NUMGENS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    numrels := tietze[TZ_NUMRELS];
    lengths := tietze[TZ_LENGTHS];

    # check the second argument to be a generator number in range.
    if not IsInt( num ) or num <= 0 or num > numgens then  Error(
        "TzEliminateGen: second argument is not a valid generator number" );
    fi;

    # determine the number of occurrences of the given generator.
    occur := TzOccurrences( tietze, num );
    occTotal := occur[1][1];
    if occTotal > 0 and occur[3][1] = 1 then

        occRelNum := occur[2][1];

        length := lengths[occRelNum];
        space := (occTotal - 1) * (length - 1) - length;

        if tietze[TZ_TOTAL] + space <= spacelimit then

            # if there is a tree of generators and if the generator to be
            # deleted is not the last generator, then delete the tree.
            if num < numgens and IsBound( T!.tree ) then
                Unbind( T!.tree );
            fi;

            # find the substituting word.
            gen := num;
            rel := rels[occRelNum];
            length := lengths[occRelNum];
            pos := Position( rel, gen );
            if pos = fail then
                gen := -gen;
                pos := Position( rel, gen );
            fi;
            word := Concatenation( rel{ [pos+1..length] },
                rel{ [1..pos-1] } );

            # replace all occurrences of gen by word^-1.
            if TzOptions(T).printLevel >= 2 then
                Print( "#I  eliminating ", gens[num], " = " );
                if Length(word)>500 then
                  Print("<word of length ",Length(word)," >\n");
                elif gen > 0 then
                    Print( AbstractWordTietzeWord( word, gens )^-1, "\n" );
                else
                    Print( AbstractWordTietzeWord( word, gens ), "\n" );
                fi;
            fi;
            TzSubstituteGen( tietze, -gen, word );

            # update the generator images, if available.
            if IsBound( T!.imagesOldGens ) then
                if gen > 0 then  word := -1 * Reversed( word );  fi;
                TzUpdateGeneratorImages( T, num, word );
            fi;

            # mark gen to be redundant.
            invs[numgens+1-num] := 0;
            tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1;
            tietze[TZ_MODIFIED] := true;
            tietze[TZ_OCCUR]:=false;
        elif TzOptions(T).printLevel >= 1 then
            Print( "#I  replacement of generators stopped by length limit\n" );
        fi;
    fi;
end );

#############################################################################
##
#M  TzEliminateGen1( <Tietze record> )  . . . . . . .  eliminates a generator
##
##  `TzEliminateGen1'  tries to  eliminate a  Tietze generator:  If there are
##  Tietze generators which occur just once in certain Tietze relators,  then
##  one of them is chosen  for which the product of the length of its minimal
##  defining word  and the  number of its  occurrences  is minimal.  However,
##  the elimination  will not be performed  if the resulting  total length of
##  the  relators   cannot  be  guaranteed   to  not  exceed   the  parameter
##  TzOptions(T).lengthLimit or the value 2^31-1.
##
InstallGlobalFunction( TzEliminateGen1, function ( T )

    local gen, gens, i,j, invs, ispace, length, lengths, modified, num,
          numgens, numrels, occur, occMultiplicities, occRelNum, occRelNums,
          occTotals, pos, protected, rel, rels, space, spacelimit, tietze,
          total, word,k,max,oldlen,bestlen,stoplen,oldrels,changed,olen;

    # check the given argument to be a Presentation.
    if not IsPresentation( T ) then
        Error( "argument must be a Presentation" );
    fi;
    TzTestInitialSetup(T); # run `1Or2Relators' if not yet done
    tietze := T!.tietze;
    protected := TzOptions(T).protected;
    spacelimit := Minimum( TzOptions(T).lengthLimit, 2^31 - 1 );

    gens := tietze[TZ_GENERATORS];
    numgens := tietze[TZ_NUMGENS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    oldrels:=ShallowCopy(rels);
    #oldrels1:=List(rels,ShallowCopy);
    numrels := tietze[TZ_NUMRELS];
    lengths := tietze[TZ_LENGTHS];

    if not IsList(tietze[TZ_OCCUR]) then
      occur := TzOccurrences( tietze );
    else
      occur :=tietze[TZ_OCCUR];
      #Print("used\n");
    fi;
#OLD_OCCUR:=List(occur,ShallowCopy);
    occTotals := occur[1];
    occRelNums := occur[2];
    occMultiplicities := occur[3];
    oldlen:=ShallowCopy(tietze[TZ_LENGTHS]);

#NEW_OCCUR:=TzOccurrences(tietze);
#if occTotals<>false and occTotals <> NEW_OCCUR[1] then
#Error("cla1");
#elif occTotals<>false and occRelNums <> NEW_OCCUR[2] then
#Error("cla2");
#elif occTotals<>false and occMultiplicities <> NEW_OCCUR[3] then
#  Error("cla3"); fi;

    modified := false;
    num := 0;
    space := 0;

    for i in [ protected + 1 .. numgens ] do
        if IsBound( occMultiplicities[i] ) and occMultiplicities[i] = 1 then
            total := occTotals[i];
            length := lengths[occRelNums[i]];
            ispace := (total - 1) * (length - 1) - length;
            if num = 0 or ispace <= space then
                num := i;
                space := ispace;
            fi;
        fi;
    od;

    if num > 0 then
      if tietze[TZ_TOTAL] + space <= spacelimit then

        # if there is a tree of generators and if the generator to be deleted
        # is not the last generator, then delete the tree.
        if num < numgens and IsBound( T!.tree ) then
            Unbind( T!.tree );
        fi;

        # find the substituting word.
        gen := num;
        occRelNum := occRelNums[num];
        rel := rels[occRelNum];
        length := lengths[occRelNum];
        pos := Position( rel, gen );
        if pos = fail then
            gen := -gen;
            pos := Position( rel, gen );
        fi;
        word := Concatenation( rel{ [pos+1..length] }, rel{ [1..pos-1] } );

        # replace all occurrences of gen by word^-1.
        if TzOptions(T).printLevel >= 2 then
            Print( "#I  eliminating ", gens[num], " = " );
            if Length(word)>500 then
              Print("<word of length ",Length(word)," >\n");
            elif gen > 0 then
                Print( AbstractWordTietzeWord( word, gens )^-1, "\n" );
            else
                Print( AbstractWordTietzeWord( word, gens ), "\n" );
            fi;
        fi;
        changed:=TzSubstituteGen( tietze, -gen, word );
        #if Length(changed)>100 then Error("longchanged!!"); fi;
        #if oldrels1<>oldrels then Error("differ!"); fi;

        # update the generator images, if available.
        if IsBound( T!.imagesOldGens ) then
            if gen > 0 then  word := -1 * Reversed( word );  fi;
            TzUpdateGeneratorImages( T, num, word );
        fi;

        # mark gen to be redundant.
        invs[numgens+1-num] := 0;
        tietze[TZ_NUMREDUNDS] := tietze[TZ_NUMREDUNDS] + 1;

        #update occurrence numbers
        gen:=AbsInt(gen);
        Unbind(occRelNums[num]);
        Unbind(occMultiplicities[num]);
        occTotals[gen]:=0;

        # now check whether the data for the other generators is still OK
        # and correct if necessary
        rels:=tietze[TZ_RELATORS];
        for i in [1..numgens] do

          if IsBound(occRelNums[i]) then
            # verify that the relator we store for the shortest
            #length is still OK.
            num:=occMultiplicities[i];
            olen:=oldlen[occRelNums[i]];

            #What can happen is two things:
            #a) A changed relator now is shorter and better. If so we take it
            #b) The best relator got changed and now is not best any more.

            # first check the changed relators, whether they give any
            # improvement
            for j in changed do
              total:=0;
              for k in rels[j] do
                if AbsInt(k)=i then total:=total+1;fi;
              od;
    #if total>0 then Print(j,":",i,":",total,"\n");fi;
              if total>0 and
                (total<num or
                (total=num and Length(rels[j])<olen) or
                (total=num and Length(rels[j])=olen and j<occRelNums[i])
                ) then
                # found a better one
                pos:=j;
                num:=total;
                olen:=Length(rels[j]);
                occMultiplicities[i]:=false; # force change
              fi;

              #update occurrence numbers
              # because of cancellation, we need to check with the changed
              # relators vs. their old selves
              for k in oldrels[j] do
                if AbsInt(k)=i then total:=total-1;fi;
              od;
              occTotals[i]:=occTotals[i]+total;

            od;

            if num<>occMultiplicities[i] or
               olen<>oldlen[occRelNums[i]] then
              occMultiplicities[i]:=num;
              occRelNums[i]:=pos;
            else
              # the changed relators did not give any improvement. We thus
              # need to check whether the best stored got worse
              if occRelNums[i] in changed then
                total:=0;
                for k in rels[occRelNums[i]] do
                  if AbsInt(k)=i then total:=total+1;fi;
                od;
                if total=0 or total>num or
                  Length(rels[occRelNums[i]])>oldlen[occRelNums[i]] then
            #Print("fixin' ",i,"\n");
                  # the relator changed and might not be good anymore. We
                  # need to find another one.

--> --------------------

--> maximum size reached

--> --------------------

Quelle tietze.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.31 Sekunden (vorverarbeitet) ]