4 New Objects and Utility Functions Provided by the AtlasRep Package
  
  This  chapter  describes  GAP objects and functions that are provided in the
  AtlasRep package but that might be of general interest.
  
  The  new objects are straight line decisions (see Section 4.1) and black box
  programs (see Section 4.2).
  
  The  new functions are concerned with representations of minimal degree, see
  Section 4.3.
  
  
  4.1 Straight Line Decisions
  
  Straight   line  decisions  are  similar  to  straight  line  programs  (see
  Section 'Reference:  Straight  Line  Programs')  but return true or false. A
  straight  line  decisions  checks  a  property  for its inputs. An important
  example  is  to  check whether a given list of group generators is in fact a
  list of standard generators (cf. Section2.3) for this group.
  
  A  straight line decision in GAP is represented by an object in the category
  IsStraightLineDecision  (4.1-1)  that stores a list of "lines" each of which
  has one of the following three forms.
  
  (1)   a nonempty dense list l of integers,
  
  (2)   a  pair  [  l,  i  ]  where l is a list of form 1. and i is a positive
        integer,
  
  (3)   a list ["Order", i, n ] where i and n are positive integers.
  
  The first two forms have the same meaning as for straight line programs (see
  Section 'Reference:  Straight  Line  Programs'), the last form means a check
  whether the element stored at the label i-th has the order n.
  
  For  the  meaning  of  the  list  of lines, see ResultOfStraightLineDecision
  (4.1-6).
  
  Straight  line  decisions  can  be  constructed  using  StraightLineDecision
  (4.1-5),    defining    attributes   for   straight   line   decisions   are
  NrInputsOfStraightLineDecision   (4.1-3)   and   LinesOfStraightLineDecision
  (4.1-2),     an     operation     for    straight    line    decisions    is
  ResultOfStraightLineDecision (4.1-6).
  
  Special  methods applicable to straight line decisions are installed for the
  operations  Display (Reference: Display), IsInternallyConsistent (Reference:
  IsInternallyConsistent),   PrintObj   (Reference:   PrintObj),  and  ViewObj
  (Reference: ViewObj).
  
  For  a straight line decision prog, the default Display (Reference: Display)
  method  prints  the  interpretation  of prog as a sequence of assignments of
  associative  words  and  of order checks; a record with components gensnames
  (with  value  a  list  of strings) and listname (a string) may be entered as
  second  argument  of  Display (Reference: Display), in this case these names
  are  used,  the  default  for  gensnames is [ g1, g2, ... ], the default for
  listname is r.
  
  4.1-1 IsStraightLineDecision
  
  > IsStraightLineDecision( obj ) ____________________________________Category
  
  Each    straight    line    decision   in   GAP   lies   in   the   category
  IsStraightLineDecision.
  
  4.1-2 LinesOfStraightLineDecision
  
  > LinesOfStraightLineDecision( prog ) _____________________________operation
  Returns:  the list of lines that define the straight line decision.
  
  This   defining   attribute   for  the  straight  line  decision  prog  (see
  IsStraightLineDecision  (4.1-1))  corresponds  to LinesOfStraightLineProgram
  (Reference: LinesOfStraightLineProgram) for straight line programs.
  
  ---------------------------  Example  ----------------------------
    gap> dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],
    > [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );
    <straight line decision>
    gap> LinesOfStraightLineDecision( dec );
    [ [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 1, 2 ], [ "Order", 2, 3 ], 
      [ "Order", 3, 5 ] ]
  ------------------------------------------------------------------
  
  4.1-3 NrInputsOfStraightLineDecision
  
  > NrInputsOfStraightLineDecision( prog ) __________________________operation
  Returns:  the number of inputs required for the straight line decision.
  
  This   defining   attribute   corresponds  to  NrInputsOfStraightLineProgram
  (Reference: NrInputsOfStraightLineProgram).
  
  ---------------------------  Example  ----------------------------
    gap> NrInputsOfStraightLineDecision( dec );
    2
  ------------------------------------------------------------------
  
  4.1-4 ScanStraightLineDecision
  
  > ScanStraightLineDecision( string ) _______________________________function
  Returns:  a record containing the straight line decision, or fail.
  
  Let  string  be  a string that encodes a straight line decision in the sense
  that  it  consists  of the lines listed for ScanStraightLineProgram (5.4-1),
  except  that  oup  lines are not allowed, and instead lines of the following
  form may occur.
  
  chor a b
        means  that  it is checked whether the order of the element at label a
        is b.
  
  ScanStraightLineDecision  returns  a  record  containing as the value of its
  component   program   the   corresponding   GAP   straight   line   decision
  (see IsStraightLineDecision  (4.1-1))  if  the  input  string  satisfies the
  syntax  rules  stated above, and returns fail otherwise. In the latter case,
  information  about the first corrupted line of the program is printed if the
  info level of InfoCMeatAxe (5.1-2) is at least 1.
  
  ---------------------------  Example  ----------------------------
    gap> str:= "inp 2\nchor 1 2\nchor 2 3\nmu 1 2 3\nchor 3 5";;
    gap> prg:= ScanStraightLineDecision( str );
    rec( program := <straight line decision> )
    gap> prg:= prg.program;;
    gap> Display( prg );
    # input:
    r:= [ g1, g2 ];
    # program:
    if Order( r[1] ) <> 2 then  return false;  fi;
    if Order( r[2] ) <> 3 then  return false;  fi;
    r[3]:= r[1]*r[2];
    if Order( r[3] ) <> 5 then  return false;  fi;
    # return value:
    true
  ------------------------------------------------------------------
  
  4.1-5 StraightLineDecision
  
  > StraightLineDecision( lines[, nrgens] ) __________________________function
  > StraightLineDecisionNC( lines[, nrgens] ) ________________________function
  Returns:  the straight line decision given by the list of lines.
  
  Let  lines  be  a list of lists that defines a unique straight line decision
  (see IsStraightLineDecision  (4.1-1));  in  this  case  StraightLineDecision
  returns this program, otherwise an error is signalled. The optional argument
  nrgens specifies the number of input generators of the program; if a list of
  integers  (a  line  of form 1. in the definition above) occurs in lines then
  this  number  is  not determined by lines and therefore must be specified by
  the argument nrgens; if not then StraightLineDecision returns fail.
  
  StraightLineDecisionNC  does  the  same as StraightLineDecision, except that
  the internal consistency of the program is not checked.
  
  4.1-6 ResultOfStraightLineDecision
  
  > ResultOfStraightLineDecision( prog, gens[, orderfunc] ) _________operation
  Returns:  true if all checks succeed, otherwise false.
  
  ResultOfStraightLineDecision    evaluates   the   straight   line   decision
  (see IsStraightLineDecision  (4.1-1)) prog at the group elements in the list
  gens.
  
  The  function for computing the order of a group element can be given as the
  optional  argument orderfunc. For example, this may be a function that gives
  up  at  a  certain  limit if one has to be aware of extremely huge orders in
  failure cases.
  
  The  result  of  a straight line decision with lines p_1, p_2, ..., p_k when
  applied to gens is defined as follows.
  
  (a)
        First  a  list  r of intermediate values is initialized with a shallow
        copy of gens.
  
  (b)
        For  i <= k, before the i-th step, let r be of length n. If p_i is the
        external  representation  of  an  associative  word  in  the  first  n
        generators  then the image of this word under the homomorphism that is
        given  by  mapping r to these first n generators is added to r. If p_i
        is  a  pair [ l, j ], for a list l, then the same element is computed,
        but  instead  of being added to r, it replaces the j-th entry of r. If
        p_i  is a triple ["Order", i, n ] then it is checked whether the order
        of r[i] is n; if not then false is returned immediately.
  
  (c)
        If  all k lines have been processed and no order check has failed then
        true is returned.
  
  Here are some examples.
  
  ---------------------------  Example  ----------------------------
    gap> dec:= StraightLineDecision( [ ], 1 );
    <straight line decision>
    gap> ResultOfStraightLineDecision( dec, [ () ] );
    true
  ------------------------------------------------------------------
  
  The  above  straight  line  decision  dec returns true –for any input of the
  right length.
  
  ---------------------------  Example  ----------------------------
    gap> dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],
    >       [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );
    <straight line decision>
    gap> LinesOfStraightLineDecision( dec );
    [ [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 1, 2 ], [ "Order", 2, 3 ], 
      [ "Order", 3, 5 ] ]
    gap> ResultOfStraightLineDecision( dec, [ (), () ] );
    false
    gap> ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,4,5) ] );
    true
  ------------------------------------------------------------------
  
  The  above  straight  line  decision admits two inputs; it tests whether the
  orders of the inputs are 2 and 3, and the order of their product is 5.
  
  
  4.1-7 Semi-Presentations and Presentations
  
  We  can  associate  a  finitely  presented group F / R to each straight line
  decision  dec,  say, as follows. The free generators of the free group F are
  in  bijection  with  the inputs, and the defining relators generating R as a
  normal  subgroup  of F are given by those words w^k for which dec contains a
  check whether the order of w equals k.
  
  So  if  dec  returns  true  for  the  input list [ g_1, g_2, ..., g_n ] then
  mapping  the  free  generators of F to the inputs defines an epimorphism Phi
  from  F  to the group G, say, that is generated by these inputs, such that R
  is contained in the kernel of Phi.
  
  (Note  that  "satisfying  dec"  is  a  stronger  property than "satisfying a
  presentation".  For example, < x | x^2 = x^3 = 1 > is a presentation for the
  trivial  group, but the straight line decision that checks whether the order
  of x is both 2 and 3 clearly always returns false.)
  
  The  ATLAS  of  Group  Representations  contains  the following two kinds of
  straight line decisions.
  
  --    A  presentation  is a straight line decision dec that is defined for a
        set  of  standard generators of a group G and that returns true if and
        only  if  the  list  of  inputs is in fact a sequence of such standard
        generators  for G. In other words, the relators derived from the order
        checks  in  the  way  described above are defining relators for G, and
        moreover these relators are words in terms of standard generators. (In
        particular  the  kernel  of  the map Phi equals R whenever dec returns
        true.)
  
  --    A  semi-presentation  is  a straight line decision dec that is defined
        for  a  set  of standard generators of a group G and that returns true
        for a list of inputs that is known to generate a group isomorphic with
        G  if  and  only  if  these inputs form in fact a sequence of standard
        generators  for G. In other words, the relators derived from the order
        checks  in  the  way  described  above  are  not  necessarily defining
        relators for G, but if we assume that the g_i generate G then they are
        standard  generators. (In particular, F / R may be a larger group than
        G  but  in  this  case  Phi  maps the free generators of F to standard
        generators of G.)
  
        More about semi-presentations can be found in [NW05].
  
  Available    presentations    and    semi-presentations    are   listed   by
  DisplayAtlasInfo  (2.5-1),  they  can  be accessed via AtlasProgram (2.5-3).
  (Clearly   each   presentation   is   also   a   semi-presentation.   So   a
  semi-presentation  for  some  standard  generators of a group is regarded as
  available  whenever  a  presentation  for these standard generators and this
  group is available.)
  
  Note   that  different  groups  can  have  the  same  semi-presentation.  We
  illustrate  this  with  an  example  that is mentioned in [NW05]. The groups
  L_2(7)  cong L_3(2) and L_2(8) are generated by elements of the orders 2 and
  3  such  that  their  product  has  order  7,  and no further conditions are
  necessary to define standard generators.
  
  ---------------------------  Example  ----------------------------
    gap> check:= AtlasProgram( "L2(8)", "check" );
    rec( program := <straight line decision>, standardization := 1, 
      identifier := [ "L2(8)", "L28G1-check1", 1, 1 ], groupname := "L2(8)" )
    gap> gens:= AtlasGenerators( "L2(8)", 1 );
    rec( generators := [ (1,2)(3,4)(6,7)(8,9), (1,3,2)(4,5,6)(7,8,9) ], 
      groupname := "L2(8)", standardization := 1, repnr := 1, 
      identifier := [ "L2(8)", [ "L28G1-p9B0.m1", "L28G1-p9B0.m2" ], 1, 9 ], 
      p := 9, id := "", size := 504 )
    gap> ResultOfStraightLineDecision( check.program, gens.generators );
    true
    gap> gens:= AtlasGenerators( "L3(2)", 1 );
    rec( generators := [ (2,4)(3,5), (1,2,3)(5,6,7) ], groupname := "L3(2)", 
      standardization := 1, repnr := 1, 
      identifier := [ "L3(2)", [ "L27G1-p7aB0.m1", "L27G1-p7aB0.m2" ], 1, 7 ], 
      p := 7, id := "a", size := 168 )
    gap> ResultOfStraightLineDecision( check.program, gens.generators );
    true
  ------------------------------------------------------------------
  
  4.1-8 AsStraightLineDecision
  
  > AsStraightLineDecision( bbox ) __________________________________attribute
  Returns:  an  equivalent  straight  line  decision  for  the given black box
            program, or fail.
  
  For    a    black    box   program   (see   IsBBoxProgram   (4.2-1))   bbox,
  AsStraightLineDecision    returns    a    straight    line   decision   (see
  IsStraightLineDecision  (4.1-1))  with the same output as bbox, in the sense
  of  AsBBoxProgram (4.2-5), if such a straight line decision exists, and fail
  otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> lines:= [ [ "Order", 1, 2 ], [ "Order", 2, 3 ],
    >              [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 3, 5 ] ];;
    gap> dec:= StraightLineDecision( lines, 2 );
    <straight line decision>
    gap> bboxdec:= AsBBoxProgram( dec );
    <black box program>
    gap> asdec:= AsStraightLineDecision( bboxdec );
    <straight line decision>
    gap> LinesOfStraightLineDecision( asdec );
    [ [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ [ 1, 1, 2, 1 ], 3 ], 
      [ "Order", 3, 5 ] ]
  ------------------------------------------------------------------
  
  4.1-9 StraightLineProgramFromStraightLineDecision
  
  > StraightLineProgramFromStraightLineDecision( dec ) ______________operation
  Returns:  the  straight  line  program associated to the given straight line
            decision.
  
  For  a  straight  line  decision  dec  (see  IsStraightLineDecision (4.1-1),
  StraightLineProgramFromStraightLineDecision   returns   the   straight  line
  program   (see   IsStraightLineProgram   (Reference:  IsStraightLineProgram)
  obtained  by  replacing  each  line of type 3. (i.e, each order check) by an
  assignment of the power in question to a new slot, and by declaring the list
  of these elements as the return value.
  
  This  means that the return value describes exactly the defining relators of
  the  presentation  that  is  associated  to  the straight line decision, see
  4.1-7.
  
  For  example,  one  can  use the return value for printing the relators with
  StringOfResultOfStraightLineProgram                              (Reference:
  StringOfResultOfStraightLineProgram),  or  for  explicitly  constructing the
  relators   as   words   in   terms   of   free   generators,   by   applying
  ResultOfStraightLineProgram  (Reference: ResultOfStraightLineProgram) to the
  program and to these generators.
  
  ---------------------------  Example  ----------------------------
    gap> dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],
    > [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );
    <straight line decision>
    gap> prog:= StraightLineProgramFromStraightLineDecision( dec );
    <straight line program>
    gap> Display( prog );
    # input:
    r:= [ g1, g2 ];
    # program:
    r[3]:= r[1]*r[2];
    r[4]:= r[1]^2;
    r[5]:= r[2]^3;
    r[6]:= r[3]^5;
    # return values:
    [ r[4], r[5], r[6] ]
    gap> StringOfResultOfStraightLineProgram( prog, [ "a", "b" ] );
    "[ a^2, b^3, (ab)^5 ]"
    gap> gens:= GeneratorsOfGroup( FreeGroup( "a", "b" ) );
    [ a, b ]
    gap> ResultOfStraightLineProgram( prog, gens );
    [ a^2, b^3, a*b*a*b*a*b*a*b*a*b ]
  ------------------------------------------------------------------
  
  
  4.2 Black Box Programs
  
  Black  box  programs  formalize the idea that one takes some group elements,
  forms  arithmetic  expressions  in  terms of them, tests properties of these
  expressions,  executes  conditional  statements  (including jumps inside the
  program)  depending  on  the  results of these tests, and eventually returns
  some result.
  
  A specification of the language can be found in [Nic06], see also
  
  http://brauer.maths.qmul.ac.uk/Atlas/info/blackbox.html.
  
  The  inputs  of  a black box program may be explicit group elements, and the
  program  may  also  ask  for random elements from a given group. The program
  steps  form  products,  inverses,  conjugates,  commutators,  etc.  of known
  elements,  tests  concern essentially the orders of elements, and the result
  is a list of group elements or true or false or fail.
  
  Examples that can be modeled by black box programs are
  
  straight line programs,
        which  require  a  fixed  number of input elements and form arithmetic
        expressions  of  elements  but  do  not  use  random  elements, tests,
        conditional statements and jumps; the return value is always a list of
        elements; these programs are described in Section 'Reference: Straight
        Line Programs'.
  
  straight line decisions,
        which  differ  from straight line programs only in the sense that also
        order  tests  are admissible, and that the return value is true if all
        these  tests  are  satisfied, and false as soon as the first such test
        fails; they are described in Section 4.1.
  
  scripts for finding standard generators,
        which take a group and a function to generate a random element in this
        group  but  no  explicit input elements, admit all control structures,
        and  return  either  a  list  of  standard  generators  or  fail;  see
        ResultOfBBoxProgram (4.2-4) for examples.
  
  In  the  case of general black box programs, currently GAP provides only the
  possibility  to read an existing program via ScanBBoxProgram (4.2-2), and to
  run  the  program using RunBBoxProgram (4.2-3). The aim is not to write such
  programs in GAP.
  
  The special case of the "find" scripts mentioned above is also admissible as
  an  argument of ResultOfBBoxProgram (4.2-4), which returns either the set of
  generators or fail.
  
  Contrary  to  the  general  situation, more support is provided for straight
  line  programs  and  straight line decisions in GAP, see Section 'Reference:
  Straight  Line  Programs'  for  functions  that  manipulate  them  (compose,
  restrict etc.).
  
  The   functions  AsStraightLineProgram  (4.2-6)  and  AsStraightLineDecision
  (4.1-8)  can  be used to transform a general black box program object into a
  straight line program or a straight line decision if this is possible.
  
  Conversely,  one  can  create an equivalent general black box program from a
  straight  line  program  or from a straight line decision with AsBBoxProgram
  (4.2-5).
  
  (Computing a straight line program related to a given straight line decision
  is  supported  in  the  sense of StraightLineProgramFromStraightLineDecision
  (4.1-9).)
  
  Note that none of these three kinds of objects is a special case of another:
  Running  a  black  box  program with RunBBoxProgram (4.2-3) yields a record,
  running a straight line program with ResultOfStraightLineProgram (Reference:
  ResultOfStraightLineProgram)  yields  a  list  of  elements,  and  running a
  straight line decision with ResultOfStraightLineDecision (4.1-6) yields true
  or false.
  
  4.2-1 IsBBoxProgram
  
  > IsBBoxProgram( obj ) _____________________________________________Category
  
  Each black box program in GAP lies in the category IsBBoxProgram.
  
  4.2-2 ScanBBoxProgram
  
  > ScanBBoxProgram( string ) ________________________________________function
  Returns:  a  record  containing  the  black box program encoded by the input
            string, or fail.
  
  For  a  string  string  that describes a black box program, e.g., the return
  value  of  StringFile  (GAPDoc:  StringFile),  ScanBBoxProgram computes this
  black  box  program. If this is successful then the return value is a record
  containing  as  the  value  of  its  component program the corresponding GAP
  object that represents the program, otherwise fail is returned.
  
  As  the  first  example, we construct a black box program that tries to find
  standard generators for the alternating group A_5; these standard generators
  are  any  pair  of  elements  of the orders 2 and 3, respectively, such that
  their product has order 5.
  
  ---------------------------  Example  ----------------------------
    gap> findstr:= "\
    >   set V 0\n\
    > lbl START1\n\
    >   rand 1\n\
    >   ord 1 A\n\
    >   incr V\n\
    >   if V gt 100 then timeout\n\
    >   if A notin 1 2 3 5 then fail\n\
    >   if A noteq 2 then jmp START1\n\
    > lbl START2\n\
    >   rand 2\n\
    >   ord 2 B\n\
    >   incr V\n\
    >   if V gt 100 then timeout\n\
    >   if B notin 1 2 3 5 then fail\n\
    >   if B noteq 3 then jmp START2\n\
    >   # The elements 1 and 2 have the orders 2 and 3, respectively.\n\
    >   set X 0\n\
    > lbl CONJ\n\
    >   incr X\n\
    >   if X gt 100 then timeout\n\
    >   rand 3\n\
    >   cjr 2 3\n\
    >   mu 1 2 4   # ab\n\
    >   ord 4 C\n\
    >   if C notin 2 3 5 then fail\n\
    >   if C noteq 5 then jmp CONJ\n\
    >   oup 2 1 2";;
    gap> find:= ScanBBoxProgram( findstr );
    rec( program := <black box program> )
  ------------------------------------------------------------------
  
  The second example is a black box program that checks whether its two inputs
  are standard generators for A_5.
  
  ---------------------------  Example  ----------------------------
    gap> checkstr:= "\
    > chor 1 2\n\
    > chor 2 3\n\
    > mu 1 2 3\n\
    > chor 3 5";;
    gap> check:= ScanBBoxProgram( checkstr );
    rec( program := <black box program> )
  ------------------------------------------------------------------
  
  4.2-3 RunBBoxProgram
  
  > RunBBoxProgram( prog, G, input, options ) ________________________function
  Returns:  a  record  describing the result and the statistics of running the
            black box program prog, or fail, or the string "timeout".
  
  For a black box program prog, a group G, a list input of group elements, and
  a record options, RunBBoxProgram applies prog to input, where G is used only
  to compute random elements.
  
  The  return value is fail if a syntax error or an explicit fail statement is
  reached  at  runtime,  and  the  string  "timeout" if a timeout statement is
  reached.  (The  latter  might  mean  that  the random choices were unlucky.)
  Otherwise a record with the following components is returned.
  
  gens
        a list of group elements, bound if an oup statement was reached,
  
  result
        true  if  a  true  statement  was  reached,  false  if  either a false
        statement or a failed order check was reached,
  
  The  other  components serve as statistical information about the numbers of
  the  various  operations (multiply, invert, power, order, random, conjugate,
  conjugateinplace, commutator), and the runtime in milliseconds (timetaken).
  
  The following components of options are supported.
  
  randomfunction
        the  function  called  with  argument  G  in order to compute a random
        element of G (default PseudoRandom (Reference: PseudoRandom))
  
  orderfunction
        the  function  for  computing  element  orders  (the  default is Order
        (Reference: Order)),
  
  quiet
        ignore echo statements (default false),
  
  verbose
        print  information  about  the  line  that is currently processed, and
        about order checks (default false),
  
  allowbreaks
        call  Error  (Reference:  Error)  when  a  break  statement is reached
        (default true).
  
  As  an example, we run the black box programs constructed in the example for
  ScanBBoxProgram (4.2-2).
  
  ---------------------------  Example  ----------------------------
    gap> g:= AlternatingGroup( 5 );;
    gap> res:= RunBBoxProgram( find.program, g, [], rec() );;
    gap> IsBound( res.gens );  IsBound( res.result );
    true
    false
    gap> List( res.gens, Order );
    [ 2, 3 ]
    gap> Order( Product( res.gens ) );
    5
    gap> res:= RunBBoxProgram( check.program, "dummy", res.gens, rec() );;
    gap> IsBound( res.gens );  IsBound( res.result );
    false
    true
    gap> res.result;
    true
    gap> othergens:= GeneratorsOfGroup( g );;
    gap> res:= RunBBoxProgram( check.program, "dummy", othergens, rec() );;
    gap> res.result;
    false
  ------------------------------------------------------------------
  
  4.2-4 ResultOfBBoxProgram
  
  > ResultOfBBoxProgram( prog, G ) ___________________________________function
  Returns:  a  list  of  group  elements  or  true, false, fail, or the string
            "timeout".
  
  This  function  calls RunBBoxProgram (4.2-3) with the black box program prog
  and  second argument either a group or a list of group elements; the default
  options  are  assumed.  The  return  value is fail if this call yields fail,
  otherwise  the  gens  component  of  the  result,  if  bound,  or the result
  component if not.
  
  As  an example, we run the black box programs constructed in the example for
  ScanBBoxProgram (4.2-2).
  
  ---------------------------  Example  ----------------------------
    gap> g:= AlternatingGroup( 5 );;
    gap> res:= ResultOfBBoxProgram( find.program, g );;
    gap> List( res, Order );
    [ 2, 3 ]
    gap> Order( Product( res ) );
    5
    gap> res:= ResultOfBBoxProgram( check.program, res );
    true
    gap> othergens:= GeneratorsOfGroup( g );;
    gap> res:= ResultOfBBoxProgram( check.program, othergens );
    false
  ------------------------------------------------------------------
  
  4.2-5 AsBBoxProgram
  
  > AsBBoxProgram( slp ) ____________________________________________attribute
  Returns:  an  equivalent  black  box  program  for  the  given straight line
            program or straight line decision.
  
  Let  slp  be  a straight line program (see IsStraightLineProgram (Reference:
  IsStraightLineProgram))     or     a    straight    line    decision    (see
  IsStraightLineDecision  (4.1-1)).  Then  AsBBoxProgram  returns  a black box
  program  bbox  (see IsBBoxProgram (4.2-1)) with the "same" output as slp, in
  the  sense  that ResultOfBBoxProgram (4.2-4) yields the same result for bbox
  as  ResultOfStraightLineProgram  (Reference: ResultOfStraightLineProgram) or
  ResultOfStraightLineDecision (4.1-6), respectively, for slp.
  
  ---------------------------  Example  ----------------------------
    gap> f:= FreeGroup( "x", "y" );;  gens:= GeneratorsOfGroup( f );;
    gap> slp:= StraightLineProgram( [ [1,2,2,3], [3,-1] ], 2 );
    <straight line program>
    gap> ResultOfStraightLineProgram( slp, gens );
    y^-3*x^-2
    gap> bboxslp:= AsBBoxProgram( slp );
    <black box program>
    gap> ResultOfBBoxProgram( bboxslp, gens );
    [ y^-3*x^-2 ]
    gap> lines:= [ [ "Order", 1, 2 ], [ "Order", 2, 3 ],
    >              [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 3, 5 ] ];;
    gap> dec:= StraightLineDecision( lines, 2 );
    <straight line decision>
    gap> ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,3,5) ] );
    true
    gap> ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,3,4) ] );
    false
    gap> bboxdec:= AsBBoxProgram( dec );
    <black box program>
    gap> ResultOfBBoxProgram( bboxdec, [ (1,2)(3,4), (1,3,5) ] );
    true
    gap> ResultOfBBoxProgram( bboxdec, [ (1,2)(3,4), (1,3,4) ] );
    false
  ------------------------------------------------------------------
  
  4.2-6 AsStraightLineProgram
  
  > AsStraightLineProgram( bbox ) ___________________________________attribute
  Returns:  an  equivalent  straight  line  program  for  the  given black box
            program, or fail.
  
  For    a    black    box   program   (see   AsBBoxProgram   (4.2-5))   bbox,
  AsStraightLineProgram    returns    a    straight    line    program    (see
  IsStraightLineProgram  (Reference:  IsStraightLineProgram))  with  the  same
  output as bbox if such a straight line program exists, and fail otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> Display( AsStraightLineProgram( bboxslp ) );
    # input:
    r:= [ g1, g2 ];
    # program:
    r[3]:= r[1]^2;
    r[4]:= r[2]^3;
    r[5]:= r[3]*r[4];
    r[3]:= r[5]^-1;
    # return values:
    [ r[3] ]
    gap> AsStraightLineProgram( bboxdec );
    fail
  ------------------------------------------------------------------
  
  
  4.3 Representations of Minimal Degree
  
  This   section   deals  with  minimal  degrees  of  permutation  and  matrix
  representations.  We do not provide an algorithm that computes these degrees
  for  an  arbitrary  group,  we  only provide some tools for evaluating known
  databases,  mainly  concerning  nearly simple groups, in order to derive the
  minimal degrees, see Section 4.3-4.
  
  In  the  AtlasRep  package,  this  information  is  used in DisplayAtlasInfo
  (2.5-1),  OneAtlasGeneratingSetInfo  (2.5-4), and AllAtlasGeneratingSetInfos
  (2.5-5).
  
  4.3-1 MinimalRepresentationInfo
  
  > MinimalRepresentationInfo( grpname, conditions ) _________________function
  Returns:  a record with the components value and source, or fail
  
  Let  groupname  be  the  GAP  name  of  a  group  G, say. If the information
  described  by  conditions about minimal representations of this group can be
  computed  or  is stored then MinimalRepresentationInfo returns a record with
  the components value and source, otherwise fail is returned.
  
  The following values for conditions are supported.
  
  --    If  conditions is NrMovedPoints (Reference: NrMovedPoints) then value,
        if   known,   is   the   degree  of  a  minimal  faithful  permutation
        representation for G.
  
  --    If  conditions  consists of Characteristic (Reference: Characteristic)
        and  a  prime  integer  p  then value, if known, is the dimension of a
        minimal faithful matrix representation in characteristic p for G.
  
  --    If  conditions  consists of Size (Reference: Size) and a prime power q
        then  value,  if  known, is the dimension of a minimal faithful matrix
        representation over the field of size q for G.
  
  In  all  cases,  the value of the component source is a list of strings that
  describe  sources  of  the information, which can be the ordinary or modular
  character  table  of G (see [CCNPW85], [JLPW95], [HL89]), the table of marks
  of  G,  or  [Jan05].  For  an overview of minimal degrees of faithful matrix
  representations  for  sporadic  simple groups and their covering groups, see
  also
  
  http://www.math.rwth-aachen.de/~MOC/mindeg/.
  
  Note  that  this  function  does  not  give  any  information  about minimal
  representations over prescribed fields in characteristic zero.
  
  Information  about  groups that occur in the AtlasRep package is precomputed
  in MinimalRepresentationInfoData (4.3-2), so the packages CTblLib and TomLib
  are  not  needed  when MinimalRepresentationInfo is called for these groups.
  (The  only  case  that  is not covered by this list is that one asks for the
  minimal  degree  of  matrix  representations  over  a  prescribed  field  in
  characteristic coprime to the group order.)
  
  One of the following strings can be given as an additional last argument.
  
  "cache"
        means  that the function tries to compute (and then store) values that
        are  not  stored  in MinimalRepresentationInfoData (4.3-2), but stored
        values are preferred; this is also the default.
  
  "lookup"
        means  that  stored  values  are  returned  but  the function does not
        attempt    to    compute    values    that    are    not   stored   in
        MinimalRepresentationInfoData (4.3-2).
  
  "recompute"
        means that the function always tries to compute the desired value, and
        checks the result against stored values.
  
  ---------------------------  Example  ----------------------------
    gap> MinimalRepresentationInfo( "A5", NrMovedPoints );
    rec( value := 5,
      source := [ "computed (alternating group)", "computed (char. table)",
          "computed (subgroup tables)",
          "computed (subgroup tables, known repres.)",
          "computed (table of marks)" ] )
    gap> MinimalRepresentationInfo( "A5", Characteristic, 2 );
    rec( value := 2, source := [ "computed (char. table)" ] )
    gap> MinimalRepresentationInfo( "A5", Size, 2 );
    rec( value := 4, source := [ "computed (char. table)" ] )
  ------------------------------------------------------------------
  
  4.3-2 MinimalRepresentationInfoData
  
  > MinimalRepresentationInfoData______________________________global variable
  
  This  is  a  record  whose  components  are  GAP  names  of groups for which
  information  about minimal permutation and matrix representations were known
  in  advance  or have been computed in the current GAP session. The value for
  the group G, say, is a record with the following components.
  
  NrMovedPoints
        a  record with the components value (the degree of a smallest faithful
        permutation  representation  of G) and source (a string describing the
        source of this information).
  
  Characteristic
        a  record  whose components are at most 0 and strings corresponding to
        prime  integers, each bound to a record with the components value (the
        degree  of  a  smallest  faithful  matrix  representation of G in this
        characteristic)  and  source  (a  string describing the source of this
        information).
  
  CharacteristicAndSize
        a  record whose components are strings corresponding to prime integers
        p,  each bound to a record with the components sizes (a list of powers
        q  of  p), dimensions (the corresponding list of minimal dimensions of
        faithful  matrix representations of G over a field of size q), sources
        (the  corresponding  list  of  strings  describing  the source of this
        information),  and complete (a record with the components val (true if
        the minimal dimension over any finite field in characteristic p can be
        derived from the values in the record, and false otherwise) and source
        (a string describing the source of this information)).
  
  The values are set by SetMinimalRepresentationInfo (4.3-3).
  
  4.3-3 SetMinimalRepresentationInfo
  
  > SetMinimalRepresentationInfo( grpname, op, value, source ) _______function
  Returns:  true  if  the values were successfully set, false if stored values
            contradict the given ones.
  
  This function sets an entry in MinimalRepresentationInfoData (4.3-2) for the
  group G, say, with GAP name grpname.
  
  Supported values for op are
  
  --    "NrMovedPoints"  (see NrMovedPoints (Reference: NrMovedPoints)), which
        means  that  value  is  the  degree  of  minimal  faithful permutation
        representations of G,
  
  --    a   list   of  length  two  with  first  entry  "Characteristic"  (see
        Characteristic  (Reference:  Characteristic))  and  second  entry char
        either  zero  or  a  prime  integer,  which  means  that  value is the
        dimension   of   minimal  faithful  matrix  representations  of  G  in
        characteristic char,
  
  --    a  list  of  length  two with first entry "Size" (see Size (Reference:
        Size)) and second entry a prime power q, which means that value is the
        dimension  of  minimal  faithful  matrix representations of G over the
        field with q elements, and
  
  --    a  list  of  length  three  with  first  entry  "Characteristic"  (see
        Characteristic  (Reference:  Characteristic)),  second  entry  a prime
        integer p, and third entry the string "complete", which means that the
        information  stored for characteristic p is complete in the sense that
        for any given power q of p, the minimal faithful degree over the field
        with q elements equals that for the largest stored field size of which
        q is a power.
  
  In each case, source is a string describing the source of the data; computed
  values are detected from the prefix "comp" of source.
  
  If the intended value is already stored and differs from value then an error
  message is printed.
  
  ---------------------------  Example  ----------------------------
    gap> SetMinimalRepresentationInfo( "A5", "NrMovedPoints", 5,
    >      "computed (alternating group)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Characteristic", 0 ], 3,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Characteristic", 2 ], 2,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Size", 2 ], 4,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Size", 4 ], 2,
    >      "computed (char. table)" );
    true
    gap> SetMinimalRepresentationInfo( "A5", [ "Characteristic", 3 ], 3,
    >      "computed (char. table)" );
    true
  ------------------------------------------------------------------
  
  
  4.3-4 Criteria Used to Compute Minimality Information
  
  Let grpname be the GAP name of a group G, say.
  
  The information about the minimal degree of a faithful matrix representation
  of  G  in  a  given  characteristic  or  over  a  given  field  in  positive
  characteristic  is derived from the relevant (ordinary or modular) character
  table  of  G, except in a few cases where this table itself is not known but
  enough information about the degrees is available in [HL89] and [Jan05].
  
  The  following  criteria  are  used  for  deriving  the  minimal degree of a
  faithful  permutation  representation  of  G from the information in the GAP
  libraries of character tables and of tables of marks.
  
  --    If grpname has the form An or An.2 (denoting alternating and symmetric
        groups,  respectively)  then  the  minimal degree is n, except if n is
        smaller than 3 or 2, respectively.
  
  --    If  grpname  has  the  form  L2(q) (denoting projective special linear
        groups in dimension two) then the minimal degree is q + 1, except if q
        in { 2, 3, 5, 7, 9, 11 }, see [Hup67, Satz II.8.28].
  
  --    If  the  largest  maximal subgroup of G is core-free then the index of
        this  subgroup  is  the  minimal  degree.  (This  is used when the two
        character tables in question and the class fusion are available in the
        GAP Character Table Library; this happens for many character tables of
        simple groups.)
  
  --    If  G  has a unique minimal normal subgroup then each minimal faithful
        permutation representation is transitive.
  
        In  this  case,  the  minimal degree can be computed directly from the
        information  in  the table of marks of G if this is available in GAP's
        library of tables of marks.
  
        Suppose  that  the  largest maximal subgroup of G is not core-free but
        simple  and normal in G, and that the other maximal subgroups of G are
        core-free.  In  this  case,  we take the minimum of the indices of the
        core-free  maximal  subgroups  and of the product of index and minimal
        degree  of  the  normal  maximal  subgroup.  (This  suffices  since no
        core-free  subgroup of the whole group can contain a nontrivial normal
        subgroup of a normal maximal subgroup.)
  
        Let  N be the unique minimal normal subgroup of G, and assume that G/N
        is  simple  and has minimal degree n, say. If there is a subgroup U of
        index n * |N| in G that intersects N trivially then the minimal degree
        of G is n * |N|. (This is used for the case that N is central in G and
        N x U occurs as a subgroup of G.)
  
  --    If  we  know a subgroup of G whose minimal degree is n, say, and if we
        know either (a class fusion from) a core-free subgroup of index n in G
        or  a  faithful permutation representation of degree n for G then n is
        the  minimal  degree  for  G. (This happens often for tables of almost
        simple groups.)
  
  4.3-5 AGR_TestMinimalDegrees
  
  > AGR_TestMinimalDegrees(  ) _______________________________________function
  Returns:  true if no contradiction was found, and false otherwise.
  
  This  function  checks  that  the  (permutation  and matrix) representations
  available  in  the ATLAS of group representations do not have smaller degree
  than the claimed minimum.
  
  An error message is printed for each contradiction found.
  
  4.3-6 BrowseMinimalDegrees
  
  > BrowseMinimalDegrees( [groupnames] ) _____________________________function
  Returns:  the list of info records for the clicked representations.
  
  If  the  GAP  package  Browse  (see  [BL08])  is  loaded  then  the function
  BrowseMinimalDegrees  is  available.  It  opens  a  browse  table whose rows
  correspond  to  the  groups  for  which  the  ATLAS of Group Representations
  contains some information about minimal degrees, whose columns correspond to
  the  characteristics  that  occur,  and  whose entries are the known minimal
  degrees.
  
  ---------------------------  Example  ----------------------------
    gap> if LoadPackage( "browse", "1.2" ) = true then
    >   down:= NCurses.keys.DOWN;;  DOWN:= NCurses.keys.NPAGE;;
    >   right:= NCurses.keys.RIGHT;;  END:= NCurses.keys.END;;
    >   enter:= NCurses.keys.ENTER;;  nop:= [ 14, 14, 14 ];;
    >   # just scroll in the table
    >   BrowseData.SetReplay( Concatenation( [ DOWN, DOWN, DOWN,
    >          right, right, right ], "sedddrrrddd", nop, nop, "Q" ) );
    >   BrowseMinimalDegrees();;
    >   # restrict the table to the groups with minimal ordinary degree 6
    >   BrowseData.SetReplay( Concatenation( "scf6",
    >        [ down, down, right, enter, enter ] , nop, nop, "Q" ) );
    >   BrowseMinimalDegrees();;
    >   BrowseData.SetReplay( false );
    > fi;
  ------------------------------------------------------------------
  
  If  an argument groupnames is given then it must be a list of group names of
  the  ATLAS  of Group Representations; the browse table is then restricted to
  the  rows  corresponding  to  these  group names and to the columns that are
  relevant  for  these  groups.  A perhaps interesting example is the subtable
  with  the  data concerning sporadic simple groups and their covering groups,
  which has been published in [Jan05]. This table can be shown as follows.
  
  ---------------------------  Example  ----------------------------
    gap> if LoadPackage( "browse", "1.2" ) = true then
    >   # just scroll in the table
    >   BrowseData.SetReplay( Concatenation( [ DOWN, DOWN, DOWN, END ],
    >          "rrrrrrrrrrrrrr", nop, nop, "Q" ) );
    >   BrowseMinimalDegrees( BibliographySporadicSimple.groupNamesJan05 );;
    > fi;
  ------------------------------------------------------------------
  
  (The  browse  table  does  not  contain rows for the groups 6.M_22, 12.M_22,
  6.Fi_22.  Note that in spite of the title of [Jan05], the entries in Table 1
  of  this  paper  are  in  fact  the  minimal degrees of faithful irreducible
  representations, and in the above three cases, these degrees are larger than
  the  minimal degrees of faithful representations. The underlying data of the
  browse table is about the minimal faithful degrees.)
  
  The    return    value    of    BrowseMinimalDegrees    is   the   list   of
  OneAtlasGeneratingSetInfo (2.5-4) values for those representations that have
  been "clicked" in visual mode.
  
  The variant without arguments of this function is also available in the menu
  shown by BrowseGapData (Browse: BrowseGapData).
  
  
  4.4 Bibliographies of Sporadic Simple Groups
  
  The  bibliographies contained in the ATLAS of Finite Groups [CCNPW85] and in
  the ATLAS of Brauer Characters [JLPW95] are available online in HTML format,
  see http://www.gap-system.org/Manuals/pkg/atlasrep/bibl/index.html.
  
  The source data in BibXMLext format is part of the AtlasRep package, in four
  files with suffix xml in the package's bibl directory. Note that each of the
  two books contains two bibliographies.
  
  Details  about  the BibXMLext format, including information how to transform
  the  data into other formats such as BibTeX, can be found in the GAP package
  GAPDoc (see [LN08]).
  
  These     source     files     are     used    also    by    the    function
  BrowseBibliographySporadicSimple (4.4-1).
  
  4.4-1 BrowseBibliographySporadicSimple
  
  > BrowseBibliographySporadicSimple(  ) _____________________________function
  Returns:  a    record   as   returned   by   ParseBibXMLExtString   (GAPDoc:
            ParseBibXMLextString).
  
  If  the  GAP  package  Browse  (see  [BL08]) is loaded then this function is
  available.  It  opens a browse table whose rows correspond to the entries of
  the  bibliographies of the ATLAS of Finite Groups [CCNPW85] and the ATLAS of
  Brauer Characters [JLPW95].
  
  The  function  is  based on BrowseBibliography (Browse: BrowseBibliography),
  see  the  documentation of this function for details, e.g., about the return
  value.
  
  The  returned record encodes the bibliography entries corresponding to those
  rows  of  the table that are "clicked" in visual mode, in the same format as
  the return value of ParseBibXMLExtString (GAPDoc: ParseBibXMLextString), see
  the manual of the GAP package GAPDoc [LN08] for details.
  
  BrowseBibliographySporadicSimple  can  be  called also via the menu shown by
  BrowseGapData (Browse: BrowseGapData).
  
  ---------------------------  Example  ----------------------------
    gap> if LoadPackage( "browse", "1.2" ) = true then
    >   enter:= NCurses.keys.ENTER;;  nop:= [ 14, 14, 14 ];;
    >   BrowseData.SetReplay( Concatenation(
    >     # choose the application
    >     "/Bibliography of Sporadic Simple Groups", [ enter, enter ],
    >     # search in the title column for the Atlas of Finite Groups
    >     "scr/Atlas of finite groups", [ enter,
    >     # and quit
    >     nop, nop, nop, nop ], "Q" ) );
    >   BrowseGapData();;
    >   BrowseData.SetReplay( false );
    > fi;
  ------------------------------------------------------------------