The functions described in this chapter have been written by Thomas Breuer, they are available since Utils 0.94.
Generalized straight line programs (in the following abbreviated as gslps) are a generalization of the straight line programs that are described in the GAP library, see Reference: Straight Line Programs. Like the latter objects, gslps describe an efficient way for evaluating an abstract word at concrete generators. The difference is that gslps can be built from existing (generalized) straight line programs, whereas a straight line program is given by an explicit list of instructions (see LinesOfStraightLineProgram (Reference: LinesOfStraightLineProgram)). So the advantages of using a gslp instead of constructing an equivalent straight line program (see EquivalentStraightLineProgram (10.1-7)) are that
available objects (the building blocks of the gslp) are reused,
the internal structure of the gslp is retained (one can access the building blocks if one wants), and
in the evaluation of a gslp, the intermediate results that arise in a building block of the gslp can be garbage collected as soon as the evaluation of this building block has finished.
A gslp in GAP is represented by an object in the category IsGeneralizedStraightLineProgram (10.1-1). This object has exactly one of the following forms.
It is a straight line program, that is, it lies in the category IsStraightLineProgram (Reference: IsStraightLineProgram), and evaluation at some group elements is defined by ResultOfStraightLineProgram (Reference: ResultOfStraightLineProgram).
It is of union
kind, that is, the defining data are a nonempty list \(l\) of gslps, and evaluation at some group elements means to evaluate the gslps in \(l\) at these group elements, and to return the concatenation of the results.
It is of compose
kind, that is, the defining data are a nonempty list \(l\) of gslps, and evaluation at some group elements means to evaluate \(l[1]\) at these elements, then to evaluate \(l[2]\) at the result of the first evaluation, and so on, and to return the last result.
Here are two typical situations where gslps arise. In both cases, suppose that a list \(l\) of standard generators for a group \(G\) is given.
Suppose that we know a straight line program for computing generators \(l'\) of a maximal subgroup \(M\) of \(G\) from \(l\). For example, these data may be taken from the ATLAS of Group Representations [WWT+]. If \(M\) is also a group for which the ATLAS of Group Representations contains generators and straight line programs, we may be interested in computing standard generators \(l''\) for \(M\) from \(l'\).
For that, a second straight line program may be needed, and it makes sense to encode the computation of \(l''\) from \(l\) via a gslp of compose
kind.
Suppose that we are in fact interested in a downward extension \(H\) of \(G\), and that \(\pi\) is the natural epimorphism from \(H\) to \(G\), which maps a list \(L\), say, of standard generators of \(H\) to \(l\). Then the above gslp for \(G\) can be applied to \(L\), but the result \(L'\) may generate a proper subgroup of \(\pi^{-1}(M)\) because some part of the kernel of \(\pi\) is missing.
A list \(K\) of generators of the kernel of \(\pi\) can be described by a straight line program that takes \(L\) as its input, and it makes sense to encode the computation of the concatenation of \(L'\) and \(K\) from \(L\) via a gslp of union
kind.
Gslps can be constructed using GeneralizedStraightLineProgram (10.1-2).
Defining attributes for gslps are NrInputsOfGeneralizedStraightLineProgram (10.1-4) and DataOfGeneralizedStraightLineProgram (10.1-3). The probably most interesting operation for gslps is ResultOfGeneralizedStraightLineProgram (10.1-6).
Currently we do not intend to provide methods applicable to generalized straight line programs for all operations that are defined for straight line programs. For example, there is no IntermediateResultOfSLP (Reference: IntermediateResultOfSLP) method for generalized straight line programs.
Special methods applicable to gslps are installed for the operations IsInternallyConsistent (10.1-8), ViewString (Reference: ViewString), and String (Reference: String).
‣ IsGeneralizedStraightLineProgram( obj ) | ( category ) |
Each generalized straight line program in GAP lies in the category IsGeneralizedStraightLineProgram. Examples are straight line programs, that is, objects in the category IsStraightLineProgram (Reference: IsStraightLineProgram).
gap> gslp:= GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program> gap> IsGeneralizedStraightLineProgram( gslp ); true gap> slp:= StraightLineProgram( [[[1,2]]], 1 ); <straight line program> gap> IsGeneralizedStraightLineProgram( slp ); true gap> IsGeneralizedStraightLineProgram( [ slp, slp ] ); false
‣ GeneralizedStraightLineProgram( lines[, nrgens] ) | ( function ) |
‣ GeneralizedStraightLineProgram( kind, list ) | ( function ) |
In the first form, lines must be a list of lists that defines a unique straight line program (see IsStraightLineProgram (Reference: IsStraightLineProgram)); in this case GeneralizedStraightLineProgram delegates to StraightLineProgram (Reference: StraightLineProgram for a list of lines (and the number of generators)).
In the second form, kind must be one of the strings "union" or "compose", and list must be a nonempty list such that each of its entries is either a gslp or a list \(l\), say, such that CallFuncList (Reference: CallFuncList) applied to GeneralizedStraightLineProgram and \(l\) returns a gslp.
gap> GeneralizedStraightLineProgram( [[[1,2]]], 1 ); <straight line program> gap> GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program> gap> GeneralizedStraightLineProgram( "compose", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program>
‣ DataOfGeneralizedStraightLineProgram( gslp ) | ( attribute ) |
For a generalized straight line program gslp that is not a straight line program, DataOfGeneralizedStraightLineProgram returns a list of length two, the first entry being either "union" or "compose" and the second being the list of defining generalized straight line programs.
If gslp is a straight line program then this attribute is not set in gslp. There is no default method to compute the value if it is not stored.
gap> gslp:= GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program> gap> DataOfGeneralizedStraightLineProgram( gslp ); [ "union", [ <straight line program>, <straight line program> ] ]
‣ NrInputsOfGeneralizedStraightLineProgram( gslp ) | ( attribute ) |
For a generalized straight line program gslp, this function returns the number of generators that are needed as input.
If gslp is a straight line program then it may be necessary that the value is set in the construction of gslp, see NrInputsOfStraightLineProgram (Reference: NrInputsOfStraightLineProgram). If gslp is not a straight line program then the value is determined by the (generalized) straight line programs from which gslp is constructed.
gap> NrInputsOfGeneralizedStraightLineProgram( > GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ) ); 1
In order to avoid the introduction of unnecessary filters, we define NrInputsOfGeneralizedStraightLineProgram just as a synonym of NrInputsOfStraightLineProgram (Reference: NrInputsOfStraightLineProgram).
‣ NrOutputsOfGeneralizedStraightLineProgram( gslp ) | ( attribute ) |
For a generalized straight line program gslp, this function returns the number of elements returned by ResultOfGeneralizedStraightLineProgram (10.1-6) when gslp is evaluated.
Note that the GAP library does not define a corresponding attribute for straight line programs.
gap> NrOutputsOfGeneralizedStraightLineProgram( > GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ) ); 2 gap> NrOutputsOfGeneralizedStraightLineProgram( > GeneralizedStraightLineProgram( "compose", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ) ); 1
‣ ResultOfGeneralizedStraightLineProgram( gslp, gens ) | ( operation ) |
ResultOfGeneralizedStraightLineProgram evaluates the generalized straight line program (see IsGeneralizedStraightLineProgram (10.1-1)) gslp at the group elements in the list gens, as follows.
If gslp is a straight line program then the value of ResultOfStraightLineProgram (Reference: ResultOfStraightLineProgram) is returned.
If gslp is of union
kind then ResultOfGeneralizedStraightLineProgram is applied to each of the involved generalized straight line programs, with second argument gens, and the concatenation of the results is returned.
If gslp is of compose
kind then ResultOfGeneralizedStraightLineProgram is first called with the first involved generalized straight line program and gens, then the operation is called with the second involved generalized straight line program and the result of this call, and so on; the last such result is returned.
gap> gens:= [ (1,2,3,4,5,6) ];; gap> gslp:= GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program> gap> ResultOfGeneralizedStraightLineProgram( gslp, gens ); [ (1,3,5)(2,4,6), (1,4)(2,5)(3,6) ] gap> gslp:= GeneralizedStraightLineProgram( "compose", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program> gap> ResultOfGeneralizedStraightLineProgram( gslp, gens ); [ () ]
In order to avoid the introduction of unnecessary operations, we define ResultOfGeneralizedStraightLineProgram just as a synonym of ResultOfStraightLineProgram (Reference: ResultOfStraightLineProgram).
‣ EquivalentStraightLineProgram( gslp ) | ( attribute ) |
For a generalized straight line program gslp, EquivalentStraightLineProgram returns a straight line program such that evaluating gslp and this straight line program with ResultOfGeneralizedStraightLineProgram (10.1-6) yields the same output, for any list of input elements.
gap> gslp:= GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program> gap> slp:= EquivalentStraightLineProgram( gslp ); <straight line program> gap> Display( slp ); # input: r:= [ g1 ]; # program: # return values: [ r[1]^2, r[1]^3 ] gap> gslp:= GeneralizedStraightLineProgram( "compose", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] ); <generalized straight line program> gap> slp:= EquivalentStraightLineProgram( gslp ); <straight line program> gap> Display( slp ); # input: r:= [ g1 ]; # program: r[2]:= r[1]^2; r[1]:= r[2]; # return values: [ r[1]^3 ]
‣ IsInternallyConsistent( gslp ) | ( method ) |
For a generalized straight line program gslp, it is checked whether all (generalized) straight line programs from which gslp is built are internally consistent, and whether their numbers of inputs and outputs are consistent and compatible with the numbers of inputs and outputs of gslp.
gap> gslp:= GeneralizedStraightLineProgram( "union", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] );; gap> IsInternallyConsistent( gslp ); true gap> gslp:= GeneralizedStraightLineProgram( "compose", > [ [ [[[1,2]]], 1 ], [ [[[1,3]]], 1 ] ] );; gap> IsInternallyConsistent( gslp ); true
generated by GAPDoc2HTML