1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2%% 3%W strategies.tex ACE documentation - strategies Alexander Hulpke 4%W Joachim Neub"user 5%W Greg Gamble 6%% 7%Y Copyright (C) 2000 Centre for Discrete Mathematics and Computing 8%Y Department of Information Tech. & Electrical Eng. 9%Y University of Queensland, Australia. 10%% 11 12%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 13\Chapter{Strategy Options for ACE} 14 15It can be difficult to select appropriate options when presented with 16a new enumeration. The problem is compounded by the fact that no 17generally applicable rules exist to predict, given a presentation, 18which option settings are ``good''. To help overcome this problem, 19{\ACE} contains various commands which select particular enumeration 20strategies. One or other of these strategies may work and, if not, the 21results may indicate how the options can be varied to obtain a 22successful enumeration. 23 24If no strategy option is passed to {\ACE}, the `default' strategy is 25assumed, which starts out presuming that the enumeration will be easy, 26and if it turns out not to be so, {\ACE} switches to a strategy 27designed for more difficult enumerations. The other straightforward 28options for beginning users are `easy' and `hard'. Thus, `easy' will 29quickly succeed or fail (in the context of the given resources); 30`default' may succeed quickly, or if not will try the `hard' strategy; 31and `hard' will run more slowly, from the beginning trying to succeed. 32 33Strategy options are merely options that set a number of the options 34seen in Chapter~"Options for ACE", all at once; they are parsed in 35*exactly* the same way as other options; order *is* important. It is 36usual to specify one strategy option and possibly follow it with a 37number of options defined in Chapter~"Options for ACE", some of which 38may over-ride those options set by the strategy option. Please refer 39to the introductory sections of Chapter~"Options for ACE", paying 40particular attention to Sections "Warnings regarding Options", "What 41happens if no ACE Strategy Option or if no ACE Option is passed", 42and~"Interpretation of ACE Options", which give various warnings, 43hints and information on the interpretation of options. 44 45There are eight strategy options. Each is passed without a value (see 46Section~"Interpretation of ACE Options") except for `sims' which 47expects one of the integer values: 1, 3, 5, 7, or 9; and, `felsch' can 48accept a value of 0 or 1, where 0 has the same effect as passing 49`felsch' with no value. Thus the eight strategy options define 50thirteen standard strategies; these are listed in the table below, 51along with all but three of the options (of Chapter~"Options for ACE") 52that they set. Additionally, each strategy sets `path = 0', `psize = 53256', and `dsize = 1000'. Recall `mend', `look' and `com' abbreviate 54`mendelsohn' (see~"option mendelsohn"), `lookahead' (see~"option 55lookahead") and `compaction' (see~"option compaction"), respectively. 56 57% \begin{table} 58% \hrule 59% \caption{The Predefined Strategies} 60% \label{tab:pred} 61% \smallskip 62% \renewcommand{\arraystretch}{0.875} 63% \begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}lrrrrrrrrrrrrr} 64% \hline\hline 65% & \multicolumn{13}{c}{parameter} \\ 66% \cline{2-14} 67% strategy & path & row & mend & no & look & com & ct & rt & fill & 68% pmode & psize & dmode & dsize \\ 69% \hline 70% default & 0 & 1 & 0 & -1 & 0 & 10 & 0 & 0 & 0 & 3 & 256 & 4 & 1000 \\ 71% easy & 0 & 1 & 0 & 0 & 0 & 100 & 0 & 1000 & 1 & 0 & 256 & 0 & 1000 \\ 72% felsch:0& 0 & 0 & 0 & 0 & 0 & 10 & 1000 & 0 & 1 & 0 & 256 & 4 & 1000 \\ 73% felsch:1 & 0 & 0 & 0 & -1 & 0 & 10 & 1000 & 0 & 0 & 3 & 256 & 4 & 1000 \\ 74% hard & 0 & 1 & 0 & -1 & 0 & 10 & 1000 & 1 & 0 & 3 & 256 & 4 & 1000 \\ 75% hlt & 0 & 1 & 0 & 0 & 1 & 10 & 0 & 1000 & 1 & 0 & 256 & 0 & 1000 \\ 76% purec & 0 & 0 & 0 & 0 & 0 & 100 & 1000 & 0 & 1 & 0 & 256 & 4 & 1000 \\ 77% purer & 0 & 0 & 0 & 0 & 0 & 100 & 0 & 1000 & 1 & 0 & 256 & 0 & 1000 \\ 78% sims:1 & 0 & 1 & 0 & 0 & 0 & 10 & 0 & 1000 & 1 & 0 & 256 & 0 & 1000 \\ 79% sims:3 & 0 & 1 & 0 & 0 & 0 & 10 & 0 & -1000 & 1 & 0 & 256 & 4 & 1000 \\ 80% sims:5 & 0 & 1 & 1 & 0 & 0 & 10 & 0 & 1000 & 1 & 0 & 256 & 0 & 1000 \\ 81% sims:7 & 0 & 1 & 1 & 0 & 0 & 10 & 0 & -1000 & 1 & 0 & 256 & 4 & 1000 \\ 82% sims:9 & 0 & 0 & 0 & 0 & 0 & 10 & 1000 & 0 & 1 & 0 & 256 & 4 & 1000 \\ 83% \hline\hline 84% \end{tabular*} 85% \end{table} 86 87\begintt 88 option 89 --------------------------------------------------------- 90strategy row mend no look com ct rt fill pmode dmode 91--------------------------------------------------------------------- 92default 1 0 -1 0 10 0 0 0 3 4 93easy 1 0 0 0 100 0 1000 1 0 0 94felsch := 0 0 0 0 0 10 1000 0 1 0 4 95felsch := 1 0 0 -1 0 10 1000 0 0 3 4 96hard 1 0 -1 0 10 1000 1 0 3 4 97hlt 1 0 0 1 10 0 1000 1 0 0 98purec 0 0 0 0 100 1000 0 1 0 4 99purer 0 0 0 0 100 0 1000 1 0 0 100sims := 1 1 0 0 0 10 0 1000 1 0 0 101sims := 3 1 0 0 0 10 0 -1000 1 0 4 102sims := 5 1 1 0 0 10 0 1000 1 0 0 103sims := 7 1 1 0 0 10 0 -1000 1 0 4 104sims := 9 0 0 0 0 10 1000 0 1 0 4 105--------------------------------------------------------------------- 106\endtt 107 108Note that we explicitly (re)set all of the listed enumerator options 109in all of the predefined strategies, even though some of them have no 110effect. For example, the `fill' value is irrelevant in HLT-type 111enumeration (see Section~"Enumeration Style"). The idea behind this is 112that, if you later change some options individually, then the 113enumeration retains the ``flavour'' of the last selected predefined 114strategy. 115 116Note also that other options which may effect an enumeration are left 117untouched by setting one of the predefined strategies; for example, 118the values of `max' (see~"option max") and `asis' (see~"option asis"). 119These options have an effect which is independent of the selected 120strategy. 121 122Note that, apart from the `felsch := 0' and `sims := 9' strategies, 123all of the strategies are distinct, although some are very similar. 124 125%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 126\Section{The Strategies in Detail} 127 128\atindex{C style}{@C style}\atindex{Cr style}{@Cr style} 129\atindex{CR style}{@CR style}\atindex{R style}{@R style} 130\atindex{R\* style}{@R\* style}\atindex{Rc style}{@Rc style} 131\atindex{R/C style}{@R/C style} 132\atindex{Defaulted R/C style}{@Defaulted R/C style} 133\atindex{R/C (defaulted) style}{@R/C (defaulted) style} 134Please note that the strategies are based on various *enumeration 135styles*: *C style*, *Cr style*, *CR style*, *R style*, *R\* style*, 136*Rc style*, *R/C style* and *defaulted R/C style*, all of which are 137described in detail in Section~"Enumeration Style". 138 139\beginitems 140 141\>`default'{option default}@{option `default'}& 142Selects the default strategy. (Shortest abbreviation: `def'.) 143 144This strategy is based on the *defaulted R/C style* (see 145Section~"Enumeration Style"). The idea here is that we assume that the 146enumeration is ``easy'' and start out in *R style*. If it turns out 147not to be easy, then we regard it as ``hard'', and switch to *CR 148style*, after performing a `lookahead' (see~"option lookahead") on the 149entire table. 150 151\>`easy'{option easy}@{option `easy'}& 152Selects an ``easy'' R style strategy. 153 154If this strategy is selected, we follow a HLT-type enumeration style, 155i.e. *R style* (see Section~"Enumeration Style"), but turn `lookahead' 156(see~"option lookahead") and `compaction' (see~"option compaction") 157off. For small and/or easy enumerations, this strategy is likely to be 158the fastest. 159 160\>`felsch'{option felsch}@{option `felsch'} 161\>`felsch:=<val>'{option felsch}@{option `felsch'}& 162Selects a Felsch strategy; <val> should be 0 or 1. 163(Shortest abbreviation: `fel'.) 164 165Here a *C style* (see Section~"Enumeration Style") enumeration is 166selected. Assigning `felsch' 0 or no value selects a pure Felsch 167strategy, and a value of 1 selects a Felsch strategy with all relators 168in the subgroup, i.e.~`no'${}=-1$ (see~"option no"), and turns 169gap-`fill'ing (see "option fill") on. 170 171\>`hard'{option hard}@{option `hard'}& 172Selects a mixed *R style* and *C style* strategy. 173 174In many ``hard'' enumerations, a mixture of *R style* and *C style* 175(see Section~"Enumeration Style") definitions, all tested in all 176essentially different positions, is appropriate. This option selects 177such a mixed strategy. The idea here is that most of the work is done 178C style (with the relators in the subgroup, i.e.~`no'${}=-1$ 179(see~"option no"), and with gap-`fill'ing (see "option fill") on), but 180that every $1000$ C style definitions a further coset number is 181applied to all relators. 182 183*Guru Notes:* 184The $1000/1$ mix is not necessarily optimal, and some experimentation 185may be needed to find an acceptable balance (see, for example, 186\cite{HR01}). Note also that, the longer the total length of the 187presentation, the more work needs to be done for each coset number 188application to the relators; one coset number application can result 189in more than $1000$ definitions, reversing the balance between R style 190and C style definitions. 191 192\>`hlt'{option hlt}@{option `hlt'}& 193Selects {\ACE}'s standard HLT strategy. 194 195Unlike Sims' \cite{Sim94} default HLT strategy, `hlt' sets the 196`lookahead' option (see~"option lookahead"). However, the option 197sequence ```hlt, lookahead := 0''' easily achieves Sims' default HLT 198strategy (recall, the ordering of options is respected; see 199Section~"Honouring of the order in which ACE Options are passed"). 200 201This is an *R style* (see Section~"Enumeration Style") strategy. 202 203\>`purec'{option purec}@{option `purec'}& 204Sets the strategy to basic *C style* (see Section~"Enumeration Style"). 205 206In this strategy there is no `compaction' (see~"option compaction"), 207no gap-`fill'ing (see "option fill") and no relators in subgroup, 208i.e.~`no'${}=0$ (see~"option no"). 209 210\>`purer'{option purer}@{option `purer'}& 211Sets the strategy to basic *R style* (see Section~"Enumeration Style"). 212 213In this strategy there is no `mendelsohn' (see "option mendelsohn"), 214no `compaction' (see~"option compaction"), no `lookahead' (see~"option 215lookahead") and no `row'-filling (see "option row"). 216 217\>`sims:=<val>'{option sims}@{option `sims'}& 218Sets a Sims strategy; <val> should be one of 1, 3, 5, 7 or 9. 219 220In his book~\cite{Sim94}, Sims discusses (and lists in Table 5.5.1) 221ten standard enumeration strategies. The Sims' strategies are 222effectively `hlt' (see~"option hlt") without `lookahead' (see~"option 223lookahead"), with or without `mendelsohn' (see~"option mendelsohn") 224set, in R (`rt' positive, `ct := 0') or R\* style (`rt' negative, `ct 225:= 0'); and `felsch' (see~"option felsch"); all either with or without 226(`lenlex') table standardisation (see Section~"Coset Table 227Standardisation Schemes" and~"ACEStandardCosetNumbering" or~"option 228standard") as the enumeration proceeds. {\ACE} does not implement 229table standardisation during an enumeration, and so only provides the 230odd-numbered strategies of Sims ({\ACE}'s numbering coincides with 231that of Sims). 232 233With care, it is often possible to duplicate the statistics given 234in~\cite{Sim94} for his odd-numbered strategies and it is also 235possible (using the interactive facilities) to approximate his 236even-numbered strategies. Examples and a more detailed exposition of 237the Sims strategies are given in Section~"Emulating Sims". 238 239\enditems 240 241%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 242%% 243%E 244