|
|
|
|
Quelle bbox.gd
Sprache: unbekannt
|
|
#############################################################################
##
#W bbox.gd GAP 4 package AtlasRep Thomas Breuer
#W Simon Nickerson
##
## This file contains the declarations of the operations
## for black box programs and straight line decisions.
##
## 1. Functions for black box algorithms
## 2. Functions for straight line decisions
##
#############################################################################
##
## 1. Functions for black box algorithms
##
## <#GAPDoc Label="BBoxIntro">
## <E>Black box programs</E> 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.
## <P/>
## A specification of the language can be found in <Cite Key="Nic06"/>,
## see also
## <P/>
## <URL>http://atlas.math.rwth-aachen.de/Atlas/info/blackbox.html</URL>.
## <P/>
## The <E>inputs</E> of a black box program may be explicit group elements,
## and the program may also ask for random elements from a given group.
## The <E>program steps</E> form products, inverses, conjugates,
## commutators, etc. of known elements,
## <E>tests</E> concern essentially the orders of elements,
## and the <E>result</E> is a list of group elements or <K>true</K> or
## <K>false</K> or <K>fail</K>.
## <P/>
## Examples that can be modeled by black box programs are
## <P/>
## <List>
## <Mark><E>straight line programs</E>,</Mark>
## <Item>
## 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 <Ref Sect="Straight Line Programs" BookName="ref"/>.
## </Item>
## <Mark><E>straight line decisions</E>,</Mark>
## <Item>
## which differ from straight line programs only in the sense that also
## order tests are admissible,
## and that the return value is <K>true</K> if all these tests are
## satisfied, and <K>false</K> as soon as the first such test fails;
## they are described
## in Section <Ref Sect="sect:Straight Line Decisions"/>.
## </Item>
## <Mark><E>scripts for finding standard generators</E>,</Mark>
## <Item>
## 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 <K>fail</K>;
## see <Ref Func="ResultOfBBoxProgram"/> for examples.
## </Item>
## </List>
## <P/>
## In the case of general black box programs, currently &GAP; provides only
## the possibility to read an existing program via
## <Ref Func="ScanBBoxProgram"/>,
## and to run the program using <Ref Func="RunBBoxProgram"/>.
## It is not our aim to write such programs in &GAP;.
## <P/>
## The special case of the <Q>find</Q> scripts mentioned above is also
## admissible as an argument of <Ref Func="ResultOfBBoxProgram"/>,
## which returns either the set of found generators or <K>fail</K>.
## <P/>
## Contrary to the general situation,
## more support is provided for straight line programs and straight line
## decisions in &GAP;,
## see Section <Ref Sect="Straight Line Programs" BookName="ref"/>
## for functions that manipulate them (compose, restrict etc.).
## <P/>
## The functions <Ref Func="AsStraightLineProgram"/> and
## <Ref Func="AsStraightLineDecision"/> 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.
## <P/>
## Conversely, one can create an equivalent general black box program from
## a straight line program or from a straight line decision with
## <Ref Func="AsBBoxProgram"/>.
## <P/>
## Computing a straight line program related to a given straight line
## decision is supported in the sense of
## <Ref Func="StraightLineProgramFromStraightLineDecision"/>.
## <P/>
## Note that none of these three kinds of objects is a special case of
## another:
## Running a black box program with <Ref Func="RunBBoxProgram"/> yields a
## record,
## running a straight line program with
## <Ref Func="ResultOfStraightLineProgram" BookName="ref"/> yields a list of
## elements,
## and running a straight line decision with
## <Ref Func="ResultOfStraightLineDecision"/> yields <K>true</K> or
## <K>false</K>.
## <#/GAPDoc>
##
#############################################################################
##
#V InfoBBox
##
## <#GAPDoc Label="InfoBBox">
## <ManSection>
## <InfoClass Name="InfoBBox"/>
##
## <Description>
## If the info level of <Ref InfoClass="InfoBBox"/> is at least <M>1</M>
## then information about <K>fail</K> results of functions dealing with
## black box programs (see Section <Ref Sect="sect:Black Box Programs"/>)
## is printed.
## The default level is <M>0</M>, no information is printed on this level.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareInfoClass( "InfoBBox" );
#############################################################################
##
#C IsBBoxProgram( <obj> )
##
## <#GAPDoc Label="IsBBoxProgram">
## <ManSection>
## <Filt Name="IsBBoxProgram" Arg='obj' Type="category"/>
##
## <Description>
## Each black box program in &GAP; lies in the filter
## <Ref Func="IsBBoxProgram"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsBBoxProgram", IsObject );
#############################################################################
##
#A LinesOfBBoxProgram( <prog> )
##
## Since no black box program can be a straight line program,
## we (ab)use the available attribute.
##
DeclareSynonymAttr( "LinesOfBBoxProgram", LinesOfStraightLineProgram );
#############################################################################
##
#F ScanBBoxProgram( <string> )
##
## <#GAPDoc Label="ScanBBoxProgram">
## <ManSection>
## <Func Name="ScanBBoxProgram" Arg='string'/>
##
## <Returns>
## a record containing the black box program encoded by the input string,
## or <K>fail</K>.
## </Returns>
## <Description>
## For a string <A>string</A> that describes a black box program, e.g.,
## the return value of <Ref Func="StringFile" BookName="gapdoc"/>,
## <Ref Func="ScanBBoxProgram"/> computes this black box program.
## If this is successful then the return value is a record containing as the
## value of its component <C>program</C> the corresponding &GAP; object
## that represents the program,
## otherwise <K>fail</K> is returned.
## <P/>
## As the first example, we construct a black box program that tries to find
## standard generators for the alternating group <M>A_5</M>;
## these standard generators are any pair of elements of the orders <M>2</M>
## and <M>3</M>, respectively, such that their product has order <M>5</M>.
## <P/>
## <Example><![CDATA[
## 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> )
## ]]></Example>
## <P/>
## The second example is a black box program that checks whether its two
## inputs are standard generators for <M>A_5</M>.
## <P/>
## <Example><![CDATA[
## 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> )
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "ScanBBoxProgram" );
#############################################################################
##
#F BBoxPerformInstruction( fullline, ins, G, ans, gpelts, ctr, options )
##
## local utility (but recursive, therefore we declare it here)
##
DeclareGlobalFunction( "BBoxPerformInstruction" );
#############################################################################
##
#F RunBBoxProgram( <prog>, <G>, <input>, <options> )
##
## <#GAPDoc Label="RunBBoxProgram">
## <ManSection>
## <Func Name="RunBBoxProgram" Arg='prog, G, input, options'/>
##
## <Returns>
## a record describing the result and the statistics of running the
## black box program <A>prog</A>, or <K>fail</K>,
## or the string <C>"timeout"</C>.
## </Returns>
## <Description>
## For a black box program <A>prog</A>, a group <A>G</A>,
## a list <A>input</A> of group elements,
## and a record <A>options</A>,
## <Ref Func="RunBBoxProgram"/> applies <A>prog</A> to <A>input</A>,
## where <A>G</A> is used only to compute random elements.
## <P/>
## The return value is <K>fail</K> if a syntax error or
## an explicit <C>fail</C> statement is reached at runtime,
## and the string <C>"timeout"</C> if a <C>timeout</C> statement is reached.
## (The latter might mean that the random choices were unlucky.)
## Otherwise a record with the following components is returned.
## <P/>
## <List>
## <Mark><C>gens</C></Mark>
## <Item>
## a list of group elements, bound if an <C>oup</C> statement was reached,
## </Item>
## <Mark><C>result</C></Mark>
## <Item>
## <K>true</K> if a <C>true</C> statement was reached,
## <K>false</K> if either a <C>false</C> statement or a failed order check
## was reached,
## </Item>
## </List>
## <P/>
## The other components serve as statistical information about the numbers
## of the various operations (<C>multiply</C>, <C>invert</C>, <C>power</C>,
## <C>order</C>, <C>random</C>, <C>conjugate</C>, <C>conjugateinplace</C>,
## <C>commutator</C>), and the runtime in milliseconds (<C>timetaken</C>).
## <P/>
## The following components of <A>options</A> are supported.
## <P/>
## <List>
## <Mark><C>randomfunction</C></Mark>
## <Item>
## the function called with argument <A>G</A> in order to compute a
## random element of <A>G</A>
## (default <Ref Oper="PseudoRandom" BookName="ref"/>)
## </Item>
## <Mark><C>orderfunction</C></Mark>
## <Item>
## the function for computing element orders
## (default <Ref Oper="Order" BookName="ref"/>),
## </Item>
## <Mark><C>quiet</C></Mark>
## <Item>
## if <K>true</K> then ignore <C>echo</C> statements
## (default <K>false</K>),
## </Item>
## <Mark><C>verbose</C></Mark>
## <Item>
## if <K>true</K> then print information about the line that is currently
## processed, and about order checks (default <K>false</K>),
## </Item>
## <Mark><C>allowbreaks</C></Mark>
## <Item>
## if <K>true</K> then call <Ref Func="Error" BookName="ref"/> when a
## <C>break</C> statement is reached, otherwise ignore <C>break</C>
## statements (default <K>true</K>).
## </Item>
## </List>
## <P/>
## As an example, we run the black box programs constructed in the example
## for <Ref Func="ScanBBoxProgram"/>.
## <P/>
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "RunBBoxProgram" );
#############################################################################
##
#F ResultOfBBoxProgram( <prog>, <G>[, <options>] )
#F ResultOfBBoxProgram( <prog>, <gens>[, <options>] )
##
## <#GAPDoc Label="ResultOfBBoxProgram">
## <ManSection>
## <Func Name="ResultOfBBoxProgram" Arg='prog, G[, options]'/>
##
## <Returns>
## a list of group elements or <K>true</K>, <K>false</K>, <K>fail</K>,
## or the string <C>"timeout"</C>.
## </Returns>
## <Description>
## This function calls <Ref Func="RunBBoxProgram"/>
## with the black box program <A>prog</A> and second argument either a group
## or a list of group elements; if <A>options</A> is not given then the
## default options of <Ref Func="RunBBoxProgram"/> are assumed.
## The return value is <K>fail</K> if this call yields <K>fail</K>,
## otherwise the <C>gens</C> component of the result, if bound,
## or the <C>result</C> component if not.
## <P/>
## Note that a <E>group</E> <A>G</A> is used as the second argument in the
## call of <Ref Func="RunBBoxProgram"/> (the source for random elements),
## whereas a <E>list</E> <A>G</A> is used as the third argument (the
## inputs).
## <P/>
## As an example, we run the black box programs constructed in the example
## for <Ref Func="ScanBBoxProgram"/>.
## <P/>
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "ResultOfBBoxProgram" );
#############################################################################
##
## 2. Functions for straight line decisions
##
#############################################################################
##
## <#GAPDoc Label="StraightLineDecisionIntro">
## <E>Straight line decisions</E> are similar to straight line programs
## (see Section <Ref Sect="Straight Line Programs" BookName="ref"/>)
## but return <K>true</K> or <K>false</K>.
## A straight line decision checks whether its inputs have some property.
## An important example is to check whether a given list of group generators
## is in fact a list of standard generators
## (cf. Section<Ref Sect="sect:Standard Generators Used in AtlasRep"/>)
## for this group.
## <P/>
## A straight line decision in &GAP; is represented by an object in the
## filter <Ref Filt="IsStraightLineDecision"/>
## that stores a list of <Q>lines</Q>
## each of which has one of the following three forms.
## <P/>
## <Enum>
## <Item>
## a nonempty dense list <M>l</M> of integers,
## </Item>
## <Item>
## a pair <M>[ l, i ]</M> where
## <M>l</M> is a list of form 1. and <M>i</M> is a positive integer,
## </Item>
## <Item>
## a list <M>[</M> <C>"Order"</C><M>, i, n ]</M>
## where <M>i</M> and <M>n</M> are positive integers.
## </Item>
## </Enum>
## <P/>
## The first two forms have the same meaning as for straight line programs
## (see Section <Ref Sect="Straight Line Programs" BookName="ref"/>),
## the last form means a check whether the element stored at the
## <M>i</M>-th label has the order <M>n</M>.
## <P/>
## For the meaning of the list of lines, see
## <Ref Oper="ResultOfStraightLineDecision"/>.
## <P/>
## Straight line decisions can be constructed using
## <Ref Func="StraightLineDecision"/>,
## defining attributes for straight line decisions are
## <Ref Func="NrInputsOfStraightLineDecision"/> and
## <Ref Func="LinesOfStraightLineDecision"/>,
## an operation for straight line decisions is
## <Ref Func="ResultOfStraightLineDecision"/>.
## <P/>
## Special methods applicable to straight line decisions are installed for
## the operations <Ref Func="Display" BookName="ref"/>,
## <Ref Func="IsInternallyConsistent" BookName="ref"/>,
## <Ref Func="PrintObj" BookName="ref"/>,
## and <Ref Func="ViewObj" BookName="ref"/>.
## <P/>
## For a straight line decision <A>prog</A>,
## the default <Ref Func="Display" BookName="ref"/> method prints
## the interpretation of <A>prog</A> as a sequence of assignments
## of associative words and of order checks;
## a record with components <C>gensnames</C> (with value a list of strings)
## and <C>listname</C> (a string) may be entered as second argument of
## <Ref Func="Display" BookName="ref"/>,
## in this case these names are used, the default for <C>gensnames</C> is
## <C>[ g1, g2, </C><M>\ldots</M><C> ]</C>,
## the default for <A>listname</A> is <M>r</M>.
## <#/GAPDoc>
##
#############################################################################
##
#C IsStraightLineDecision( <obj> )
##
## <#GAPDoc Label="IsStraightLineDecision">
## <ManSection>
## <Filt Name="IsStraightLineDecision" Arg='obj' Type="category"/>
##
## <Description>
## Each straight line decision in &GAP; lies in the filter
## <Ref Func="IsStraightLineDecision"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsStraightLineDecision", IsObject );
#############################################################################
##
#F StraightLineDecision( <lines>[, <nrgens>] )
#F StraightLineDecisionNC( <lines>[, <nrgens>] )
##
## <#GAPDoc Label="StraightLineDecision">
## <ManSection>
## <Func Name="StraightLineDecision" Arg='lines[, nrgens]'/>
## <Func Name="StraightLineDecisionNC" Arg='lines[, nrgens]'/>
##
## <Returns>
## the straight line decision given by the list of lines.
## </Returns>
## <Description>
## Let <A>lines</A> be a list of lists that defines a unique
## straight line decision (see <Ref Func="IsStraightLineDecision"/>);
## in this case <Ref Func="StraightLineDecision"/> returns this program,
## otherwise an error is signalled.
## The optional argument <A>nrgens</A> 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 <A>lines</A> then this number is not determined by <A>lines</A>
## and therefore <E>must</E> be specified by the argument <A>nrgens</A>;
## if not then <Ref Func="StraightLineDecision"/> returns <K>fail</K>.
## <P/>
## <Ref Func="StraightLineDecisionNC"/> does the same as
## <Ref Func="StraightLineDecision"/>,
## except that the internal consistency of the program is not checked.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "StraightLineDecision" );
DeclareGlobalFunction( "StraightLineDecisionNC" );
#############################################################################
##
#A LinesOfStraightLineDecision( <prog> )
##
## <#GAPDoc Label="LinesOfStraightLineDecision">
## <ManSection>
## <Oper Name="LinesOfStraightLineDecision" Arg='prog'/>
##
## <Returns>
## the list of lines that define the straight line decision.
## </Returns>
## <Description>
## This defining attribute for the straight line decision <A>prog</A>
## (see <Ref Func="IsStraightLineDecision"/>) corresponds to
## <Ref Attr="LinesOfStraightLineProgram" BookName="ref"/>
## for straight line programs.
## <P/>
## <Example><![CDATA[
## 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 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "LinesOfStraightLineDecision", IsStraightLineDecision );
#############################################################################
##
#A NrInputsOfStraightLineDecision( <prog> )
##
## <#GAPDoc Label="NrInputsOfStraightLineDecision">
## <ManSection>
## <Oper Name="NrInputsOfStraightLineDecision" Arg='prog'/>
##
## <Returns>
## the number of inputs required for the straight line decision.
## </Returns>
## <Description>
## This defining attribute corresponds to
## <Ref Attr="NrInputsOfStraightLineProgram" BookName="ref"/>.
## <P/>
## <Example><![CDATA[
## gap> NrInputsOfStraightLineDecision( dec );
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "NrInputsOfStraightLineDecision", IsStraightLineDecision );
#############################################################################
##
#O ResultOfStraightLineDecision( <prog>, <gens>[, <orderfunc>] )
##
## <#GAPDoc Label="ResultOfStraightLineDecision">
## <ManSection>
## <Oper Name="ResultOfStraightLineDecision" Arg='prog, gens[, orderfunc]'/>
##
## <Returns>
## <K>true</K> if all checks succeed, otherwise <K>false</K>.
## </Returns>
## <Description>
## <Ref Oper="ResultOfStraightLineDecision"/> evaluates the straight line
## decision (see <Ref Func="IsStraightLineDecision"/>) <A>prog</A>
## at the group elements in the list <A>gens</A>.
## <P/>
## The function for computing the order of a group element can be given as
## the optional argument <A>orderfunc</A>.
## 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.
## <P/>
## The <E>result</E> of a straight line decision with lines
## <M>p_1, p_2, \ldots, p_k</M>
## when applied to <A>gens</A> is defined as follows.
## <P/>
## <List>
## <Mark>(a)</Mark>
## <Item>
## First a list <M>r</M> of intermediate values is initialized
## with a shallow copy of <A>gens</A>.
## </Item>
## <Mark>(b)</Mark>
## <Item>
## For <M>i \leq k</M>, before the <M>i</M>-th step,
## let <M>r</M> be of length <M>n</M>.
## If <M>p_i</M> is the external representation of an associative word
## in the first <M>n</M> generators then the image of this word
## under the homomorphism that is given by mapping <M>r</M>
## to these first <M>n</M> generators is added to <M>r</M>.
## If <M>p_i</M> is a pair <M>[ l, j ]</M>, for a list <M>l</M>,
## then the same element is computed,
## but instead of being added to <M>r</M>,
## it replaces the <M>j</M>-th entry of <M>r</M>.
## If <M>p_i</M> is a triple <M>[ </M><C>"Order"</C><M>, i, n ]</M>
## then it is checked whether the order of <M>r[i]</M> is <M>n</M>;
## if not then <K>false</K> is returned immediately.
## </Item>
## <Mark>(c)</Mark>
## <Item>
## If all <M>k</M> lines have been processed and no order check
## has failed then <K>true</K> is returned.
## </Item>
## </List>
## <P/>
## Here are some examples.
## <P/>
## <Example><![CDATA[
## gap> dec:= StraightLineDecision( [ ], 1 );
## <straight line decision>
## gap> ResultOfStraightLineDecision( dec, [ () ] );
## true
## ]]></Example>
## <P/>
## The above straight line decision <C>dec</C> returns <K>true</K>
## –for <E>any</E> input of the right length.
## <P/>
## <Example><![CDATA[
## 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
## ]]></Example>
## <P/>
## The above straight line decision admits two inputs;
## it tests whether the orders of the inputs are <M>2</M> and <M>3</M>,
## and the order of their product is <M>5</M>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "ResultOfStraightLineDecision",
[ IsStraightLineDecision, IsHomogeneousList ] );
DeclareOperation( "ResultOfStraightLineDecision",
[ IsStraightLineDecision, IsHomogeneousList, IsFunction ] );
#############################################################################
##
## <#GAPDoc Label="Semi-Presentations">
## <Subsection Label="Semi-Presentations and Presentations">
## <Heading>Semi-Presentations and Presentations</Heading>
##
## <Index>semi-presentation</Index>
## We can associate a <E>finitely presented group</E> <M>F / R</M>
## to each straight line decision <A>dec</A>, say, as follows.
## The free generators of the free group <M>F</M> are in bijection
## with the inputs, and the defining relators generating <M>R</M> as a
## normal subgroup of <M>F</M> are given by those words <M>w^k</M>
## for which <A>dec</A> contains a check whether the order of <M>w</M>
## equals <M>k</M>.
## <P/>
## So if <A>dec</A> returns <K>true</K> for the input list
## <M>[ g_1, g_2, \ldots, g_n ]</M> then mapping the free generators of
## <M>F</M> to the inputs defines an epimorphism <M>\Phi</M> from <M>F</M>
## to the group <M>G</M>, say, that is generated by these inputs,
## such that <M>R</M> is contained in the kernel of <M>\Phi</M>.
## <P/>
## (Note that <Q>satisfying <A>dec</A></Q> is a stronger property than
## <Q>satisfying a presentation</Q>.<Index>presentation</Index>
## For example, <M>\langle x \mid x^2 = x^3 = 1 \rangle</M>
## is a presentation for the trivial group, but the straight line decision
## that checks whether the order of <M>x</M> is both <M>2</M> and <M>3</M>
## clearly always returns <K>false</K>.)
## <P/>
## &AtlasRep; supports the following two kinds of straight line decisions.
## <P/>
## <List>
## <Item>
## A <E>presentation</E> is a straight line decision <A>dec</A>
## that is defined for a set of standard generators of a group <M>G</M>
## and that returns <K>true</K> if and only if the list of inputs is
## in fact a sequence of such standard generators for <M>G</M>.
## In other words, the relators derived from the order checks in the way
## described above are defining relators for <M>G</M>,
## and moreover these relators are words in terms of standard generators.
## (In particular the kernel of the map <M>\Phi</M> equals <M>R</M>
## whenever <A>dec</A> returns <K>true</K>.)
## </Item>
## <Item>
## A <E>semi-presentation</E> is a straight line decision <A>dec</A>
## that is defined for a set of standard generators of a group <M>G</M>
## and that returns <K>true</K> for a list of inputs <E>that is known to
## generate a group isomorphic with <M>G</M></E> if and only if
## these inputs form in fact a sequence of standard generators for
## <M>G</M>.
## In other words, the relators derived from the order checks in the way
## described above are <E>not necessarily defining relators</E>
## for <M>G</M>, but if we assume that the <M>g_i</M> generate <M>G</M>
## then they are standard generators.
## (In particular, <M>F / R</M> may be a larger group than <M>G</M>
## but in this case <M>\Phi</M> maps the free generators of <M>F</M>
## to standard generators of <M>G</M>.)
## <P/>
## More about semi-presentations can be found in <Cite Key="NW05"/>.
## </Item>
## </List>
## <P/>
## Available presentations and semi-presentations are listed by
## <Ref Func="DisplayAtlasInfo"/>,
## they can be accessed via <Ref Func="AtlasProgram"/>.
## (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.)
## <P/>
## Note that different groups can have the same semi-presentation.
## We illustrate this with an example that is mentioned in
## <Cite Key="NW05"/>.
## The groups <M>L_2(7) \cong L_3(2)</M> and <M>L_2(8)</M> are generated by
## elements of the orders <M>2</M> and <M>3</M> such that their product has
## order <M>7</M>, and no further conditions are necessary to define
## standard generators.
## <P/>
## <Example><![CDATA[
## gap> check:= AtlasProgram( "L2(8)", "check" );
## rec( groupname := "L2(8)",
## identifier := [ "L2(8)", "L28G1-check1", 1, 1 ],
## program := <straight line decision>, standardization := 1,
## version := "1" )
## gap> gens:= AtlasGenerators( "L2(8)", 1 );
## rec( charactername := "1a+8a", constituents := [ 1, 6 ],
## contents := "core",
## generators := [ (1,2)(3,4)(6,7)(8,9), (1,3,2)(4,5,6)(7,8,9) ],
## groupname := "L2(8)", id := "",
## identifier := [ "L2(8)", [ "L28G1-p9B0.m1", "L28G1-p9B0.m2" ], 1, 9
## ], isPrimitive := true, maxnr := 1, p := 9, rankAction := 2,
## repname := "L28G1-p9B0", repnr := 1, size := 504,
## stabilizer := "2^3:7", standardization := 1, transitivity := 3,
## type := "perm" )
## gap> ResultOfStraightLineDecision( check.program, gens.generators );
## true
## gap> gens:= AtlasGenerators( "L3(2)", 1 );
## rec( contents := "core", generators := [ (2,4)(3,5), (1,2,3)(5,6,7) ],
## groupname := "L3(2)", id := "a",
## identifier := [ "L3(2)", [ "L27G1-p7aB0.m1", "L27G1-p7aB0.m2" ], 1,
## 7 ], isPrimitive := true, maxnr := 1, p := 7, rankAction := 2,
## repname := "L27G1-p7aB0", repnr := 1, size := 168,
## stabilizer := "S4", standardization := 1, transitivity := 2,
## type := "perm" )
## gap> ResultOfStraightLineDecision( check.program, gens.generators );
## true
## ]]></Example>
## </Subsection>
## <#/GAPDoc>
##
#############################################################################
##
#O StraightLineProgramFromStraightLineDecision( <dec> )
##
## <#GAPDoc Label="StraightLineProgramFromStraightLineDecision">
## <ManSection>
## <Oper Name="StraightLineProgramFromStraightLineDecision" Arg='dec'/>
##
## <Returns>
## the straight line program associated to the given straight line decision.
## </Returns>
## <Description>
## For a straight line decision <A>dec</A>
## (see <Ref Func="IsStraightLineDecision"/>,
## <Ref Oper="StraightLineProgramFromStraightLineDecision"/> returns the
## straight line program
## (see <Ref Func="IsStraightLineProgram" BookName="ref"/> 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.
## <P/>
## This means that the return value describes exactly the defining relators
## of the presentation that is associated to the straight line decision,
## see <Ref Subsect="Semi-Presentations and Presentations"/>.
## <P/>
## For example, one can use the return value for printing the relators with
## <Ref Func="StringOfResultOfStraightLineProgram" BookName="ref"/>,
## or for explicitly constructing the relators as words in terms of free
## generators,
## by applying <Ref Func="ResultOfStraightLineProgram" BookName="ref"/>
## to the program and to these generators.
## <P/>
## <Example><![CDATA[
## 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)^5 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "StraightLineProgramFromStraightLineDecision",
[ IsStraightLineDecision ] );
#############################################################################
##
#A AsBBoxProgram( <slp> )
#A AsBBoxProgram( <dec> )
##
## <#GAPDoc Label="AsBBoxProgram">
## <ManSection>
## <Attr Name="AsBBoxProgram" Arg='slp'/>
##
## <Returns>
## an equivalent black box program for the given straight line program
## or straight line decision.
## </Returns>
## <Description>
## Let <A>slp</A> be a straight line program
## (see <Ref Func="IsStraightLineProgram" BookName="ref"/>)
## or a straight line decision (see <Ref Func="IsStraightLineDecision"/>).
## Then <Ref Attr="AsBBoxProgram"/> returns a black box program <A>bbox</A>
## (see <Ref Func="IsBBoxProgram"/>) with the <Q>same</Q> output as
## <A>slp</A>,
## in the sense that <Ref Func="ResultOfBBoxProgram"/> yields the same
## result for <A>bbox</A>
## as <Ref Func="ResultOfStraightLineProgram" BookName="ref"/> or
## <Ref Func="ResultOfStraightLineDecision"/>, respectively, for <A>slp</A>.
## <P/>
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AsBBoxProgram", IsStraightLineProgram );
DeclareAttribute( "AsBBoxProgram", IsStraightLineDecision );
#############################################################################
##
#A AsStraightLineProgram( <bbox> )
##
## <#GAPDoc Label="AsStraightLineProgram">
## <ManSection>
## <Attr Name="AsStraightLineProgram" Arg='bbox'/>
##
## <Returns>
## an equivalent straight line program for the given black box program,
## or <K>fail</K>.
## </Returns>
## <Description>
## For a black box program (see <Ref Attr="AsBBoxProgram"/>) <A>bbox</A>,
## <Ref Func="AsStraightLineProgram"/> returns a straight line program
## (see <Ref Func="IsStraightLineProgram" BookName="ref"/>) with the same
## output as <A>bbox</A> if such a straight line program exists,
## and <K>fail</K> otherwise.
## <P/>
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AsStraightLineProgram", IsBBoxProgram );
#############################################################################
##
#A AsStraightLineDecision( <bbox> )
##
## <#GAPDoc Label="AsStraightLineDecision">
## <ManSection>
## <Attr Name="AsStraightLineDecision" Arg='bbox'/>
##
## <Returns>
## an equivalent straight line decision for the given black box program,
## or <K>fail</K>.
## </Returns>
## <Description>
## For a black box program (see <Ref Func="IsBBoxProgram"/>) <A>bbox</A>,
## <Ref Func="AsStraightLineDecision"/> returns a straight line decision
## (see <Ref Func="IsStraightLineDecision"/>) with the same
## output as <A>bbox</A>, in the sense of <Ref Attr="AsBBoxProgram"/>,
## if such a straight line decision exists,
## and <K>fail</K> otherwise.
## <P/>
## <Example><![CDATA[
## 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 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AsStraightLineDecision", IsBBoxProgram );
#############################################################################
##
#E
[ Dauer der Verarbeitung: 0.37 Sekunden
(vorverarbeitet)
]
|
2026-03-28
|
|
|
|
|
