[Up] [Previous] [Next] [Index]

5 Strategy Options for ACE

Sections

  1. The Strategies in Detail

It can be difficult to select appropriate options when presented with a new enumeration. The problem is compounded by the fact that no generally applicable rules exist to predict, given a presentation, which option settings are ``good''. To help overcome this problem, ACE contains various commands which select particular enumeration strategies. One or other of these strategies may work and, if not, the results may indicate how the options can be varied to obtain a successful enumeration.

If no strategy option is passed to ACE, the default strategy is assumed, which starts out presuming that the enumeration will be easy, and if it turns out not to be so, ACE switches to a strategy designed for more difficult enumerations. The other straightforward options for beginning users are easy and hard. Thus, easy will quickly succeed or fail (in the context of the given resources); default may succeed quickly, or if not will try the hard strategy; and hard will run more slowly, from the beginning trying to succeed.

Strategy options are merely options that set a number of the options seen in Chapter Options for ACE, all at once; they are parsed in exactly the same way as other options; order is important. It is usual to specify one strategy option and possibly follow it with a number of options defined in Chapter Options for ACE, some of which may over-ride those options set by the strategy option. Please refer to the introductory sections of Chapter Options for ACE, paying particular attention to Sections Warnings regarding Options, What happens if no ACE Strategy Option or if no ACE Option is passed, and Interpretation of ACE Options, which give various warnings, hints and information on the interpretation of options.

There are eight strategy options. Each is passed without a value (see Section Interpretation of ACE Options) except for sims which expects one of the integer values: 1, 3, 5, 7, or 9; and, felsch can accept a value of 0 or 1, where 0 has the same effect as passing felsch with no value. Thus the eight strategy options define thirteen standard strategies; these are listed in the table below, along with all but three of the options (of Chapter Options for ACE) that they set. Additionally, each strategy sets path = 0, psize = 256, and dsize = 1000. Recall mend, look and com abbreviate mendelsohn (see option mendelsohn), lookahead (see option lookahead) and compaction (see option compaction), respectively.

                               option
            ---------------------------------------------------------
strategy    row  mend  no  look  com    ct     rt  fill  pmode  dmode
---------------------------------------------------------------------
default       1     0  -1     0   10     0      0     0      3      4
easy          1     0   0     0  100     0   1000     1      0      0
felsch := 0   0     0   0     0   10  1000      0     1      0      4
felsch := 1   0     0  -1     0   10  1000      0     0      3      4
hard          1     0  -1     0   10  1000      1     0      3      4
hlt           1     0   0     1   10     0   1000     1      0      0
purec         0     0   0     0  100  1000      0     1      0      4
purer         0     0   0     0  100     0   1000     1      0      0
sims := 1     1     0   0     0   10     0   1000     1      0      0
sims := 3     1     0   0     0   10     0  -1000     1      0      4
sims := 5     1     1   0     0   10     0   1000     1      0      0
sims := 7     1     1   0     0   10     0  -1000     1      0      4
sims := 9     0     0   0     0   10  1000      0     1      0      4
---------------------------------------------------------------------

Note that we explicitly (re)set all of the listed enumerator options in all of the predefined strategies, even though some of them have no effect. For example, the fill value is irrelevant in HLT-type enumeration (see Section Enumeration Style). The idea behind this is that, if you later change some options individually, then the enumeration retains the ``flavour'' of the last selected predefined strategy.

Note also that other options which may effect an enumeration are left untouched by setting one of the predefined strategies; for example, the values of max (see option max) and asis (see option asis). These options have an effect which is independent of the selected strategy.

Note that, apart from the felsch := 0 and sims := 9 strategies, all of the strategies are distinct, although some are very similar.

5.1 The Strategies in Detail

Please note that the strategies are based on various enumeration styles: C style, Cr style, CR style, R style, R* style, Rc style, R/C style and defaulted R/C style, all of which are described in detail in Section Enumeration Style.

  • default
    Selects the default strategy. (Shortest abbreviation: def.)

    This strategy is based on the defaulted R/C style (see Section Enumeration Style). The idea here is that we assume that the enumeration is ``easy'' and start out in R style. If it turns out not to be easy, then we regard it as ``hard'', and switch to CR style, after performing a lookahead (see option lookahead) on the entire table.

  • easy
    Selects an ``easy'' R style strategy.

    If this strategy is selected, we follow a HLT-type enumeration style, i.e. R style (see Section Enumeration Style), but turn lookahead (see option lookahead) and compaction (see option compaction) off. For small and/or easy enumerations, this strategy is likely to be the fastest.

  • felsch
  • felsch:=val
    Selects a Felsch strategy; val should be 0 or 1. (Shortest abbreviation: fel.)

    Here a C style (see Section Enumeration Style) enumeration is selected. Assigning felsch 0 or no value selects a pure Felsch strategy, and a value of 1 selects a Felsch strategy with all relators in the subgroup, i.e. no=−1 (see option no), and turns gap-filling (see option fill) on.

  • hard
    Selects a mixed R style and C style strategy.

    In many ``hard'' enumerations, a mixture of R style and C style (see Section Enumeration Style) definitions, all tested in all essentially different positions, is appropriate. This option selects such a mixed strategy. The idea here is that most of the work is done C style (with the relators in the subgroup, i.e. no=−1 (see option no), and with gap-filling (see option fill) on), but that every 1000 C style definitions a further coset number is applied to all relators.

    Guru Notes: The 1000/1 mix is not necessarily optimal, and some experimentation may be needed to find an acceptable balance (see, for example, HR01). Note also that, the longer the total length of the presentation, the more work needs to be done for each coset number application to the relators; one coset number application can result in more than 1000 definitions, reversing the balance between R style and C style definitions.

  • hlt
    Selects ACE's standard HLT strategy.

    Unlike Sims' Sim94 default HLT strategy, hlt sets the lookahead option (see option lookahead). However, the option sequence ``hlt, lookahead := 0'' easily achieves Sims' default HLT strategy (recall, the ordering of options is respected; see Section Honouring of the order in which ACE Options are passed).

    This is an R style (see Section Enumeration Style) strategy.

  • purec
    Sets the strategy to basic C style (see Section Enumeration Style).

    In this strategy there is no compaction (see option compaction), no gap-filling (see option fill) and no relators in subgroup, i.e. no=0 (see option no).

  • purer
    Sets the strategy to basic R style (see Section Enumeration Style).

    In this strategy there is no mendelsohn (see option mendelsohn), no compaction (see option compaction), no lookahead (see option lookahead) and no row-filling (see option row).

  • sims:=val
    Sets a Sims strategy; val should be one of 1, 3, 5, 7 or 9.

    In his book Sim94, Sims discusses (and lists in Table 5.5.1) ten standard enumeration strategies. The Sims' strategies are effectively hlt (see option hlt) without lookahead (see option lookahead), with or without mendelsohn (see option mendelsohn) set, in R (rt positive, ct := 0) or R* style (rt negative, ct := 0); and felsch (see option felsch); all either with or without (lenlex) table standardisation (see Section Coset Table Standardisation Schemes and ACEStandardCosetNumbering or option standard) as the enumeration proceeds. ACE does not implement table standardisation during an enumeration, and so only provides the odd-numbered strategies of Sims (ACE's numbering coincides with that of Sims).

    With care, it is often possible to duplicate the statistics given in Sim94 for his odd-numbered strategies and it is also possible (using the interactive facilities) to approximate his even-numbered strategies. Examples and a more detailed exposition of the Sims strategies are given in Section Emulating Sims.

  • [Up] [Previous] [Next] [Index]

    ACE manual
    February 2020