Automatic groups associated with word orders other than shortlex

Sarah Rees, Department of Mathematics, University of Newcastle, Newcastle NE1 7RU, UK, e-mail: Sarah.Rees@ncl.ac.uk

Abstract

The existing algorithm to compute and verify the automata associated with an automatic group deals only with the subclass of shortlex automatic groups. This paper describes the extension of the algorithm to deal with automatic groups associated with other word orders (the algorithm has now been implemented) and reports on the use of the algorithm for specific examples; in particular a very natural automatic (or asynchonously automatic) structure for the Baumslag-Solitar and related classes of groups (closely related to one described for some of those groups by Epstein et al.) is found from a wreath product order over shortlex.

AMS subject classifications: 20F10, 20-04, 68Q40, secondary classification: 03D40.

1 Introduction

The definition of an automatic group grew out of work of Cannon ([3]) in an attempt to formalise properties observed in the fundamental groups of compact hyperbolic manifolds. Briefly (a formal definition will be given below), an automatic group is a group satisfying certain finiteness conditions which allow the group to be described by a set of finite state automata; one finite state automaton defines a language, or set of words in the generators, which contains at least one representative of each group element, the others describe multiplication between words in that language. The book [6] provides a standard reference.

∗The author would like to thank both the Lehrstuhl D für Mathematik of the RWTH-Aachen, and the New York Group Theory Cooperative for their hospitality during the period of the research described in this paper, Derek Holt and David Epstein for helpful discussions, and the referee for valuable comments. The visit to Aachen was funded by the European Union HCM grant no. ERBCHRXCT930418

Using the automata associated with an automatic group, the ‘word problem’ can be solved, and the group elements efficiently enumerated. The growth function of the language for the defined group defined by the first automaton can be computed (this will be the growth function of the group if the language consists of unique geodesic representatives of the group elements). Some group theoretical properties (such as torsion) can sometimes be read from the automata. Thus it is interesting not merely to know that a group is automatic, but also to be able to construct explicitly the associated automata, and hence to compute information about the group. In [7] and [12], descriptions are given of two variations of a procedure which successfully construct these automata for groups which are automatic with respect to the shortlex word order (see below for a definition of this subclass); the Warwick packages automata and its recent successor kbmag implement these ideas. Further a procedure originally described by Epstein, and now developed and implemented by P. Wakefield ([24]) constructs a further short automatic structure from the shortlex automatic structure of a word hyperbolic group (and so verifies hyperbolicity). However, although many topologically interesting groups are known to be shortlex or short automatic, some classes have only been shown to be automatic with respect to other word orders, while for other groups, geometrical considerations, or the existence of a finite rewriting system with respect to a word order other than shortlex make it interesting to look for different kinds of automatic structures.

The purpose of this paper is to describe a generalisation of the original shortlex procedure to construct the automata associated with a wider class of automatic groups, and hence verify automaticity for these groups. The procedure is designed in as general way as possible; it can be used for any reduction word order for which two particular ingredients can be defined. Most of the procedure is valid also for orders which are translation invariant but not actually reduction orders.

The procedure was initially implemented in C ++ within the New York based Magnus system ([15]) for computation in group theory, specifically for the weighted orders wtlex and wtshortlex; in this implementation, it makes use of C. Sims’ rkbp implementation of the Knuth-Bendix procedure ([23]), and parts of D. Holt’s kbmag package for Knuth-Bendix and automatic groups. It has now been implemented within the GAP language ([22]), currently specifically for the wtlex order and the wreath product order over shortlex; in this implementation it also makes use of parts of the kbmag package. The code is available on request.

The paper is divided into six sections, of which the first is this introduction. Section 2 contains the definition of an automatic group. Section 3 outlines the tools and basic steps of the procedure to verify automaticity; this is modelled on the Warwick shortlex procedure, but at some points needs to be more general. Section 4 describes the general construction of a word acceptor, this being the part of the procedure which needs substantial modification. The construction in section 4 is dependent on the particular order only to the extent that it requires the definition of the two ingredients already mentioned, that is (in the terms of this paper) a history function f and a finite sufficient set H of difference histories for that order; section 5 explains how f and H may be defined for each of the wtlex order, the wtshortlex order, and wreath product orders over shortlex. Finally, section 6 looks at some examples of applications of the procedure for the above orders. In particular the structures obtained for the Baumslag-Solitar and related classes of groups seem to be interesting.

2 Definition of an automatic group

Throughout this paper G will denote a finitely presented group defined by the presentation

G = ⟨g_{1}, g_{2}, …, g_{m} | x_{1} = y_{1}, …, x_{k} = y_{k}⟩.

We shall use the term generator of G to mean any element of the set {g_{1}, …, g_{m}, g_{1}^{−1}, …, g_{m}^{−1}}, and word in the generators of G to mean any string of symbols from the set {g_{1}, …, g_{m}, g_{1}^{−1}, …, g_{m}^{−1}}.

For words w, w′ in the generators of G, w = w′ will mean that w and w′ are identical as strings, while w =_{G} w′ will mean that w and w′ represent the same group element of G. Futher, l(w) will denote the string length of w (for example, l(g_{1}^{5}g_{2}^{−3}) = 8) and l_{G}(w) the string length of a shortest word u with u =_{G} w. For any integer i, w(i) will denote the prefix of w of length i if i < l(w), and will otherwise denote the whole of w. We shall use the symbol ϵ to denote the word of length 0, and e to denote the identity element of the group G (which ϵ represents).

For the purposes of this paper, a finite state automaton M is a finite directed graph, whose edges are labelled by symbols from an associated set known as its alphabet. Out of each state there is at most one edge labelled with any given alphabet symbol. One vertex (or state) is known as the start state, some of the others are accept states. A string on the alphabet is accepted (and so is in the language, L(M), of M) if it labels a path from the start state to an accept state, and is otherwise rejected. Since transitions out of some states on some symbols may be undefined, an automaton satisfying these conditions is often known as a partial deterministic automaton. A set of words is called a regular set if it is the language of a finite state automaton.

A 2-stringed automaton is a finite state automaton whose alphabet is a set of ordered pairs of symbols from a base alphabet. The language can be considered as a set of pairs of words over the base alphabet; pairs of words are read by the automaton by reading at each stage a pair of symbols, one from each string. If one word is longer than the other, then the shorter word is padded out with a padding symbol, which we shall denote by , until the two words are equal in length.

Definition 2.1 (Automatic group) G = ⟨g_{1}, g_{2}, …, g_{m}⟩ is automatic if

(i) there is a finite state automaton W with alphabet {g_{1}, …, g_{m}, g_{1}^{−1}, …, g_{m}^{−1}} whose language L(W) contains at least one representative of each element of G.

(ii) there is a constant K such that, if v, w ∈ L(W), and l_{G}(v^{−1}w) ≤ 1, then, for all i, l_{G}(v(i)^{−1}w(i)) ≤ K.

Condition (ii) is known as the fellow traveller property. It can be replaced in the definition (and often is) by the following condition:-

(ii)* for each element g of the set {e, g_{1}, …, g_{m}, g_{1}^{−1}, …, g_{m}^{−1}}, there is a 2stringed finite state automaton M_{g}, with base alphabet {g_{1}, …, g_{m}, g_{1}^{−1}, …, g_{m}^{−1}} whose language is the set of pairs of words (v, w) from L(W) such that vg =_{G} w.

For the purposes of computational verification of an automatic structure, (ii)* is sometimes more appropriate than the more geometrical condition (ii).

W is called the word acceptor, and M_{g} the multiplier for g. The word acceptor and multipliers together form an automatic structure for the group, and L(W) the associated language. Using the multipliers, any word can be reduced to a representative in the language.

The above definition of automaticity appears to be dependent on the choice of generators for G. In fact it is not (see [6]). It is straightforward to deduce that G is finitely presented.

The class of automatic groups includes finite groups, free groups, free abelian groups, various small-cancellation groups ([9]), Coxeter groups ([2]), Artin groups of finite and large type ([4, 5, 18, 13]), Braid groups ([6], chapter 9), word-hyperbolic groups and so, in particular, (see [3]), all co-compact discrete groups of isometries of n-dimensional hyperbolic space. However the class includes, for example, no virtually nilpotent group which is not virtually abelian.

Many of the languages associated with automatic structures are naturally associated with an easily described word order.

Definition 2.2 (Automatic with respect to a word order) Let ⪯ be any partial order on words. A word v is said to be irreducible with respect to ⪯ if there is no word u with u =_{G} v and u ≺ v (that is with u ≠ v and u ⪯ v).

A group G is said to be automatic with respect to ⪯ if there is an automatic structure for G for which the language is the set of all irreducible words with respect to ⪯.

Free abelian groups, Coxeter groups, and all word hyperbolic groups are automatic with respect to shortlex, or ‘shortlex automatic’, (for shortlex, u ≺ v if u is shorter than v, or if u and v have the same length but u precedes v lexicographically, in relation to a fixed order on the group generators and their inverses).

However for some groups, other languages are known to give automatic structures. By [6], Theorem 3.4.5, word hyperbolic groups are short automatic, that is automatic with language the set of all geodesic words; Papasoglu ( [17]) showed that this property characterises word hyperbolic groups. The fundamental groups of geometrically finite hyperbolic manifolds were proved by Epstein ([6], Chapter 11) to be wtlex automatic (given some weight function on words, u ≺ v in wtlex if u has lower weight than v or if u and v have the same weight and u precedes v lexicographically). A new result by Urs Lang ([14]) now proves these groups also to be shortlex automatic. Small cancellation groups satisfying the conditions C(6) − P, C(4) − T (4) − P or C(3) − T (6) − P, which are not in general word hyperbolic, are proved in [9] to be automatic, with a language derived from a set of geodesic words. Braid groups and more generally Artin groups of finite type are proved to be automatic with a language associated with a ‘left greedy’ word order, and large type Artin groups (extra large, by [18], large by [13]) with respect to an order based on a combination of length, lexicographical order, and the natural order of associated binary strings. Finally Lee Mosher ([16]) has proved that the mapping class group of a surface of finite type is automatic with a language which is decribed geometrically in terms of triangulations on the surface.

Note that, whenever G is automatic it is automatic with respect to the partial order ⪯ defined by

u ⪯ v ⟺ v = u or v =_{G} u, u ∈ L(G), v ∉ L(G)

However we shall be interested in the case where ⪯ is a reduction order, that is, a translation invariant linear order (u ⪯ v implies both au ⪯ av and ub ⪯ vb for all strings a, b) with no infinite descending chains v_{1} ≻ v_{2} ≻ … v_{n} ≻ . . ..

3 The basic steps of the procedure to verify automaticity

Most of the theory and procedure of this section is simply a translation of the shortlex automatic procedure of [7] and [12] into more general language. The main difficulty is in the construction of the word acceptor, and the associated reduction procedure, where, although the same basic principle is used, a great deal more care needs to be taken.

3.1 The word difference machine

An automaton known as a word difference machine, described below, is crucial to the procedure we shall describe for constructing and verifying an automatic structure.

Suppose that G is automatic with language L. The fellow traveller property implies that the set D_{L} of all minimal representatives (under any specified reduction order) of elements v(i)^{−1}u(i), with v, u ∈ L and l_{G}(v^{−1}u) ≤ 1, is finite. The elements of D_{L} are known as word differences.

We can define a 2-stringed automaton with the elements of D_{L} as states, in a natural way. We consider the empty word ϵ to be the start state, all states to be accept states, and define transitions on pairs of generators. We define a transition from the start state to itself on every pair (g, g). In addition, for d, d′ ∈ D we define a transition on the pair (g, h) from d to d′ if for distinct words v, u ∈ L, with l_{G}(v^{−1}u) ≤ 1, and with i-th generators g, h,

d =_{G} v(i − 1)^{−1}u(i − 1), d′ =_{G} v(i)^{−1}u(i).

There are no other transitions. Where v (or u) has length less than i, its prefix v(i) (or u(i)) of length i is interpreted in the above as the whole string, and g (or h) is interpreted as the padding symbol.

We call the automaton thus defined the difference machine for L (and we use the notation D_{L} for it, as well as for the underlying set of word differences). The procedure we shall describe hinges on the construction of a machine which estimates D_{L}, and which we shall also call a difference machine.

Definition 3.1 (Difference machine) We define a difference machine for G to be a 2-stringed automaton D, with base alphabet X, satisfying the following properties:-

(i) all of the states of D are accept states;

(ii) each of the states of D is labelled by a word in the generators of G, known as a word difference;

(iii) the start state is labelled by the trivial word;

(iv) if d, d′ are word differences, and if there is a transition from the state corresponding to d to the state corresponding to d′ under the pair (g, h), then g^{−1}dh =_{G} d′;

(v) for all g ∈ X, there is a transition from the start state to the start state on (g, g).

If (w_{1}, w_{2}) is accepted by D, d_{w_{1},w_{2}} is defined to be the label of the target of (w_{1}, w_{2}); condition (iv) ensures that d_{w_{1},w_{2}} is a word representing w_{1}^{−1}w_{2}.

Clearly D_{L} as defined above is a difference machine according to this definition.

Condition (v) might be omitted. It makes the descriptions which follow in this paper more straightforward; but from an implementation point of view makes the difference machine bigger than it needs to be, and hence those transitions may not actually be stored, although the algorithms need to take account of them.

For notational convenience, we shall also define, for any word difference d ∈ D, an automaton D^{d} which has the same states and transitions as D but only the single accept state d. Thus, for example, for any pair of words (w_{1}, w_{2}) accepted by D^{ϵ}, w_{1} =_{G} w_{2}.

Definition 3.2 (Fellow travellers) If (w_{1}, w_{2}) is a pair of words accepted by a difference machine D, then we shall say that w_{1} and w_{2} D-fellow travel.

Note that condition (v) in the definition of a difference machine ensures that whenever w_{1} and w_{2} D-fellow travel then so do cw_{1} and cw_{2} for any word c. However w_{1}c and w_{2}c might not.

The label d_{w_{1},w_{2}} of the target of the pair (w_{1}, w_{2}) in D, is a word representing the product w_{1}^{−1}w_{2}. In theory it could happen that w_{1} and w_{2} D-fellow travel but w_{2} and w_{1} do not. In practice it will not happen in this paper. For in this paper, we shall often need our difference machines to satisfy the conditions defined below; of these, inverse closure ensures that w_{2} and w_{1} D-fellow travel whenever w_{1} and w_{2} do.

Definition 3.3 (Inverse closure, substring closure, minimal labelling) Let D be a difference machine.

We say that D is inverse closed if for each word difference d, a word in G representing the inverse of d is also a word difference, and whenever there is a transition from d to d′ under (g, h) there is a transition from d′ to d under (g^{−1}, h^{−1}).

We say that D is substring closed if for each word difference d both the maximal prefix d_{1} of d and the maximal suffix d_{2} of d are word differences, and where d = d_{1}g = h^{−1}d_{2} (for generators g and h), there is a transition from d_{1} to d under ( , g) and from d_{2} to d under (h, ).

Finally we say that D is minimally labelled (with respect to an order ⪯) if the word w which labels the state d is the least of all words w_{1}^{−1}w_{2} such that (w_{1}, w_{2}) labels a path to d.

Suppose from now on that ⪯ is translation invariant. Note that, in this case, any one of the above properties can be verified for a given difference machine D in finite time, and further, if any of them fail, a difference machine D′ can be constructed in finite time, whose language contains the language of D, and in which those properties hold.

To describe our procedure, we need the concepts of reducibility and irreducibility relative to a difference machine D

Definition 3.4 (D-reducible, D-irreducible) If u, v are words such that u =_{G} v, u ≺ v and u = au′b, v = av′b for some a, b and some pair (v′, u′) accepted by D^{ϵ}, we say that v is D-reducible, with direct D-reduction u; w is then called a D-reduction of v if there is a chain u_{0} = v, u_{1}, …, u_{k} = w, with k > 0 such that each u_{i} is a direct D-reduction of u_{i−1}. We say that v is D-irreducible if it is not D-reducible.

Further we say that v is minimally D-reducible if it is D-reducible, but every proper subword of it is D-irreducible. We say that v is directly D-reducible if v is D-reducible, with some direct D-reduction which is D-irreducible.

If D = D_{L}, for some automatic group with language L, then L can be defined as the set of all D-irreducible words. That all words in L are D-irreducible is clear. To see that L contains all D-irreducible words, notice that if v is a word not in L, then v = v_{1}xv_{2} for words v_{1}, v_{2} and a generator x such that v_{1} ∈ L, but v_{1}x ∉ L. Then where u ∈ L is equal to v_{1}x in G, certainly u ≺ v_{1}x and u and v_{1}x D_{L}-fellow travel. So v is D_{L}-reducible with direct D_{L}-reduction uv_{2}.

If D = D_{L}, then every minimally D-reducible word is directly D-reducible; this follows from the above and the fellow traveller property for L. However this will not in general be true.

3.2 Defining the automatic structure in terms of the difference machine

Suppose that ⪯ is a translation invariant linear order. If G is automatic with respect to ⪯, with language L, then the automatic structure is completely determined by the automaton D_{L} and ⪯.

The word acceptor can be defined as the finite state automaton which accepts all D_{L}-irreducible words; the construction of this is described in section 4. The multiplier M_{g} can be defined as the automaton which accepts (v, w) if v and w are both accepted by W and (v, w) is accepted by D_{L}^{d}, where d = d_{ϵ,g} (a word difference which represents g). Thus, a standard construction builds M_{g} out of the automata W and D_{L}^{d}.

D_{L} can also be used to reduce a word to a representative in L. Given a word w, we trace pairs of words (v, u) (for each substring v of w) through D_{L}, and look for a pair (v, u) which is accepted by D_{L}^{ϵ} and for which u ≺ v. If such a pair exists, v reduces to u, and hence w also reduces. Iteration gives complete reduction.

3.3 The procedure as a whole

A construction to compute and verify an automatic structure with respect to the shortlex order (and hence prove a group shortlex automatic) is described in [7] and [12]. Here we describe the procedure in greater generality, in order to apply it to other orders ⪯.

The essential differences are in the details of the construction of the word acceptor, and in the procedure to reduce a word to one equal to it and accepted by the word acceptor. However we shall first describe the procedure as a whole, for greater clarity.

Briefly, a finite set of word differences is accumulated and an associated difference machine built, which is an estimate for the machine D_{L}; the automata W and M_{g} described above are constructed from this. If G is automatic with respect to ⪯ and if further the difference machine is indeed D_{L}, then these will be the automata of an automatic structure, but otherwise one of a series of tests will fail. Some test failures indicate word differences which have not so far been found, and allow a modification of the difference machine, and then the reconstruction of the automata. If the group is automatic with respect to ⪯, then provided that the initial phase to accumulate word differences is run for ‘long enough’, after a finite number of loops the automatic structure will be found. (For some automatic groups the initial phase cannot find all word differences, and so some looping is essential.) However, if the group is not automatic with respect to ⪯, or even if it is but the initial phase was not run for long enough, the procedure may never terminate.

In fact the procedure described in [7] and [12] for shortlex uses two different estimates for D_{L}, at different stages; a smaller difference machine is used for the construction of the word acceptor than for the construction of the multipliers. We choose not to do that.

For the full procedure we require ⪯ to be a reduction order; otherwise the first step, in which the Knuth-Bendix ([10]) procedure is run, does not make sense. However much of the procedure depends only on ⪯ being translation invariant.

The basic steps of the full procedure are as follows:-

Step 1: Where G = ⟨g_{j} | x_{k} = y_{k}⟩ and y_{k} ⪯ x_{k}, initialise a set R of rewriting

rules to be

{x_{k} → y_{k}, g_{j}g_{j}^{−1} → 1, g_{j}^{−1}g_{j} → 1}.

Run the Knuth-Bendix procedure on R for some time.

At any stage, given the rewriting system R, define a related difference machine D as follows. The states of D are all reductions (by R) of words of the form x(i)^{−1}y(i) such that x → y or y → x is a rule in R. For generators g, h, there is a transition on the pair (g, h) from d to d′ if g^{−1}dh reduces in R to d′. Similarly there a transition on (g, ) or ( , h) from d to d′ if g^{−1}d or dh reduces in R to d′.

If the Knuth-Bendix procedure terminates with a finite, confluent set of rules, or if otherwise D appear to stabilise, move on to step 2.

Step 2: Construct a word acceptor W, as a finite state automaton which accepts all D-irreducible words, and does not accept both w and w′ if w′ is a D-reduction of w. Jump to step 4.

Step 3: If this step is entered, D has just been modified. If W now accepts words w, w′ such that w′ is a D-reduction of w, go back to step 2. Otherwise, continue to step 4.

Step 4: For each generator g, construct M_{g} to accept a string (v, w) if and only if v ∈ L(W), w ∈ L(W), (v, w) ∈ L(D), and the target word difference of the pair (v, w) is d_{ϵ,g}. Define M_{e} to accept (v, v) if and only if v is accepted by W.

Step 5: For each M_{g}, use standard automaton operations to check if the set

{v : ∃w, (v, w) ∈ L(M_{g})}

is equal to L(W). If this is true for all g, continue to step 6. If not, then for some g a word v can be identified in L(W) for which no (v, w) is accepted by M_{g}. Where w is the reduction of vg computed using the difference machine D, compute and reduce the word differences associated with the equation vg = w, add them and the appropriate transitions to D, and go back to step 3.

Step 6: For each of the defining relators r = g_{i_{1}}g_{i_{2}} … g_{i_{k}} of G, and also for each of the words r = xx^{−1}, where x is a generator, compute an automaton M_{r}, which accepts (v, w) if for some v = v_{0}, v_{1}, v_{2}, …, v_{k} = w, (v_{j−1}, v_{j}) is accepted by M_{g_{i_{j}}}. The group is proved automatic with the machines W and all the M_{g} defining its automatic structure if for each such r, M_{r} accepts the same language as M_{e}.

If the Knuth-Bendix procedure does not terminate, then there is some room for interpretation as to when the machine D is considered to be stable. If G is automatic, then at some stage during the Knuth-Bendix procedure, D must contain all the information necessary to build the word acceptor. However it might never contain enough infomation to build correct multipliers. For when (v, w) is accepted by the correct automaton M_{g}, it can easily happen that the reduction rule vg → w would never be found by the Knuth Bendix procedure, but is only a consequence of a sequence of such rules.

If the Knuth-Bendix procedure terminates with a finite, confluent set, then a word acceptor may be built directly from that set, rather than from the difference machine; it is simply defined to reject a word if and only if it contains the left hand side of a rewrite rule as a substring. However, even in that case, the difference machine D computed from the rewrite system may not be large enough to build correct multipliers; indeed the group may not be automatic.

Step 5 checks to see if the language defined by the word acceptor W satisfies the fellow traveller property. If step 5 completes successfully, then the automata W, M_{e}, M_{g_{1}}, M_{g_{1}^{−1}}, …, M_{g_{m}}, M_{g_{m}^{−1}} form an automatic structure for a monoid H of which G is a quotient.

Step 6 checks to see if the relations of G hold in H; if they do then G and H are isomorphic, and so G is automatic with the given automatic structure. If they do not it is because the Knuth-Bendix procedure was halted prematurely, some word differences were missed, and so W accepts two different words which are equal in the group. If the Knuth-Bendix procedure in step 1 terminated with a confluent set, then step 6 is unnecessary, and may be omitted.

4 The general construction of the word acceptor

4.1 The basic idea

Suppose that ⪯ is a translation invariant linear order, and that D is an inverse closed and substring closed difference machine. (Such a difference machine can easily be constructed from a given one, if that machine does not already have the required properties.) Provided that ⪯ satisfies certain conditions (that is, admits the definition of the two essential ingredients, f and H, as defined below), the construction we shall describe below terminates with a finite state automaton W which accepts all D-irreducible words for ⪯. W may also accept some words which are D-reducible, but will not accept both w and w′ if w′ is a D-reduction of w. If L(D) ⊇ L(D_{L}), where L is the language of an automatic structure, then L(W) must be the set of all D-irreducible words.

Where ⪯ is the shortlex word order, it is straightforward to construct a machine W which recognises precisely the D-irreducible words. For in this case, there is a finite state automaton GT which accepts a pair (v, u) of words precisely when v ≻ u. Then W can be defined as the machine which rejects w if for some prefix v of w there is a word u such that (v, u) is accepted both by GT and by D^{ϵ}, more precisely

L(W) = (X^{∗} \ {v : ∃u, (v, u) ∈ L(GT) ∩ L(D^{ϵ})})X^{∗}

Since the class of finite state automata is closed under each of the logical operations and, not and ∃, and there are terminating algorithms to perform those operations, there is a clear terminating algorithm to compute the word acceptor in this case.

However, for a general word order ⪯ the set of pairs (v, u) with v ≻ u is not a regular language, and so there is no finite state automaton to recognise it; instead we define a mechanism (equivalent to a finite state automaton, although we describe it in a different language) to recognise a large enough subset of that language for our purposes.

4.2 The ingredients of the general construction

There are two basic ingredients for the general construction, a history function f, and a set H of difference histories, which is both finite and sufficient for reduction. All these terms will now be explained.

First we look for a way to encode the essential information for the comparison of two words under ≻. For this we use a history function.

Definition 4.1 (History function) Let ⪯ be a translation invariant linear order on the set of words over some alphabet A. We define a history function for ⪯ to be a function f, defined on pairs (v, u) of distinct words over A with l(v) ≥ l(u), such that

(a) the sets of values of f on {(v, u) : l(v) = l(u)} and {(v, u) : l(v) > l(u)} are disjoint;

(b) for any word c, and any (v, u) with l(v) ≥ l(u), f((v, u)) = f((cv, cu));

(c) for any (v, u) with v ≠ u and l(v) = l(u), knowledge of f(v, u) is enough to decide

(i) for any given words a, b whether or not va ≻ ub, (ii) for any given generators g, h, the value of f(vg, uh);

(d) for any (v, u) with l(v) > l(u), knowledge of f(v, u) is enough to decide

(i) for any given word a, whether or not va ≻ u, (ii) for any given generator g, the value of f(vg, u).

We call the image of a pair of words or a set of pairs of words under f its history.

A little thought shows that a history function for shortlex can be defined by

f(v, u) = (1, 0) if l(v) > l(u)
= (0, 1) if l(v) = l(u) and v ≻ u
= (0, 0) if l(v) = l(u) and v ≺ u

In general if ⪯ is a word order for which the set of pairs (v, u) with v ≻ u is regular, recognised by a finite state automaton GT, then the function f which maps (v, u) onto the target of (v, u) in GT is a history function.

For any v, in order to predict whether or not some word of the form va is minimally D-reducible, we need to consider pairs of words (v, u), for which u is no longer than v, and D-fellow travels with v. If for some a, va is minimally D-reducible, then for some such u, some ub is a direct D-reduction of va; the pair (d_{v,u}, f(v, u)), carries enough information to recognise this. Hence, for any D-reducible word w, we can locate a D-reduction of w by systematically computing all such pairs (d_{v,u}, f(v, u)) for which v is a prefix of w, and for each such, where g is the generator in w following the prefix v, testing to see whether vg reduces to some ub. An iteration of this procedure reduces w to a D-irreducible word w′, with w′ =_{G} w.

This motivates our definition of a difference history.

Definition 4.2 (Difference history) Let D be a difference machine, ⪯ a translation invariant word order, and f a history function for ⪯. For any word v, we define a difference history δ for v (with respect to (D, f)) to be a pair (d, f(v, u)) such that v ≠ u, l(v) ≥ l(u), (v, u) ∈ L(D), and d = d_{v,u}. We define f^{−1}(δ) to be the set of all pairs (v′, u′) of distinct words with l(v′) ≥ l(u′) associated with the word difference d for which f(v′, u′) = f(v, u). Where H is a set of difference histories, we define f^{−1}(H) analogously.

Definition 4.3 (Target of a difference history) Let δ = (d, f(v, u)) be a difference history, and suppose that g, h are generators.

If the target of d under (g, h) is a non-identity word difference d′, and if l(v) = l(u), then the target of δ under (g, h) is defined to be the difference history (d′, f(vg, uh)), otherwise the target of δ under (g, h) is undefined.

If the target of d under (g, ) is a non-identity word difference d′′, then the target of δ under (g, ) is defined to be the difference history (d′′, f(vg, u)), otherwise the target of δ under (g, ) is undefined.

When f has finite range, we have basically defined the states and transitions of a finite state automata, whose states are the difference histories. However, in general we cannot find f with finite range. If we are only interested in accumulating the tree of difference histories necessary to D-reduce a single word, this is not a problem; however we need to be more careful in order to use the same mechanism to build a word acceptor, since otherwise the construction might not terminate.

We deal with this problem by restricting consideration to a proper subset of the set of difference histories; we hope to find an appropriate subset which is also finite.

Definition 4.4 Let H be a set of difference histories for f.

Where v is minimally D-reducible, we say that H carries a reduction for v (to u) if u is a D-reduction of v such that for every proper prefix v(i) of v, (v(i), u(i)) is in f^{−1}(H). More generally, where v is any D-reducible word, we say that H carries a reduction of v if it carries a reduction for some minimally D-reducible subword of v.

H is said to be sufficient for reduction if for any minimally D-reducible word v

either H carries a reduction for v

or v is not directly D-reducible, and H carries a reduction for every direct D-reduction of v.

Of course the set of all difference histories is always sufficient, but we are in particular interested in sets which are both sufficient and finite.

4.3 Using f and H to build the word acceptor

Suppose from now on that we have a history function f, and a set of difference histories H which is both sufficient and finite.

Briefly, we construct a word acceptor by building outwards from the start state. First the target of the start state under each generator g is defined, either to be failure, or to be a set of difference histories in H, and those targets which are not the failure state are put on a queue to be dealt with. From then on, states are taken off the queue one at a time, and for each, its target under each generator is computed (as described below), as a set of difference histories; this may then be identified either as the set corresponding to an existing state, or as a new state. Each time a new state is found it is put onto the end of the queue. The word acceptor is complete when the queue is empty.

The procedure is designed so that the state s of the word acceptor reached by tracing out a non-trivial accepted word w corresponds to a set of difference histories for w. For any g, when the target of s under g is an accept state, it will correspond to a set of difference histories which are the targets of the difference histories associated with s.

We shall prove that the construction terminates, given that H is finite, and yields a correct word acceptor, given that H is sufficient.

For any word order ⪯ for which the language of pairs (v, u) with v ≻ u is regular, the language of a finite state automaton GT, the construction below is a natural construction of the machine to recognise the language

(X^{∗} \ {v : ∃u, (v, u) ∈ L(GT) ∩ L(D^{ϵ})})X^{∗},

when f simply maps (v, u) onto the target state of (v, u) in GT, and H is simply the set of all difference histories.

First we give the details of the construction.

Where s_{0} is the start state, for each generator g :

define the target of s_{0} under g to be failure if for some (not necessarily non-trivial) word z with z ≺ g, (g, z) is accepted by D^{ϵ};

otherwise define the target t of s_{0} under g to correspond to the set of difference histories in H

{(d, f(g, h)) : d = d_{g,h} ∈ D, h is a generator or ϵ}

and add t to the end of the queue.

For each state s on the queue in turn, for each generator g :

define the target of s under g to be failure if either the target of the start state under g is failure (in this case g itself reduces), or for some difference history δ associated with s, with associated word difference d, one of the following situations occurs:-

either (a) the target of d under (g, ) is accepted by D^{ϵ} (and so, g^{−1}d =_{G}

e) and examination of δ shows that if (v, u) ∈ f^{−1}(δ), then u ≺ vg, or (b) there exists a generator h such that the target of d under (g, h)

is accepted by D^{ϵ} (and so, g^{−1}dh =_{G} e) and examination of δ shows that if (v, u) ∈ f^{−1}(δ), then uh ≺ vg,

or (c) there exists a generator h such that the target of d under (g, h) is a word difference d′, and examination of δ shows that, where d′′ is the word difference inverse to d′, if (v, u) ∈ f^{−1}(δ), then uhd′′ ≺ vg;

otherwise define the target t of s under g to correspond to the set of difference histories in H which are targets under (g, h), with h a generator or ϵ, of difference histories in the set corresponding to the state s, together with all difference histories in H which are associated with the target in the word acceptor of s_{0} under g.

Proposition 4.5 Let ⪯ be a translation invariant linear order, and let D be an inverse closed and substring closed difference machine. When f is a history function for (⪯, D), and H a finite sufficient set of difference histories for f, the above construction terminates and constructs an automaton which accepts all D-irreducible words, and cannot accept both w and w′ if w′ is the D-reduction of w.

Proof: Termination is guaranteed by the finiteness of H; H can thus only have finitely many subsets to correspond to states.

The construction ensures that the state s which is the target of an accepted string w is associated with a set of difference histories δ each of the form (d, f(v, u)) for some suffix v of w. If wg is rejected, then for some difference history (d, (v, u)) associated with s, and for u′ defined to be either u, uh for some generator h, or uhd′′, we have u′ =_{G} vg and u′ ≺ vg. Since v is a suffix of w, we have wg = avg for some a. Then vg and u′ D-fellow travel, since v and u do (where u′ = uhd′′ we use the fact that D is inverse and substring closed). Hence so do wg and au′. So wg is D-reducible, with D-reduction au′.

This proves that every string rejected by the automaton is D-reducible, and hence that any D-irreducible word must be accepted.

Now suppose that w is any word for which H carries a reduction. We show that W rejects w.

The word w can be written in the form avb for some minimally D-reducible v for which H carries a reduction. Then, there is some u ≺ v such that for each proper prefix v(i) of v, the pair (v(i), u(i)) is in f^{−1}(H). Let v = g_{j_{1}}g_{j_{2}} … g_{j_{r}}, and let u = h_{j_{1}}h_{j_{2}} … h_{j_{r′}}. Since v is minimally D-reducible, g_{j_{1}} ≠ h_{j_{1}}. If r′ < r, now define h_{j_{i}} to be the padding symbol for i > r′, for ease of notation.

Let s be the target of the start state under a, and for each i ≤ l(v), let s_{i} be the target of the start state under av(i). (We may assume without loss of generality that these are all defined, since otherwise certainly w is rejected.)

Since each (v(i), u(i)) is in f^{−1}(H), difference histories δ_{i} = (d_{i}, f(v(i), u(i))) ∈ H, can be defined for each i, and δ_{i} is the target of δ_{i−1} under (g_{j_{i}}, h_{j_{i}}) for any i > 1. δ_{1} is associated with the target of the start state under (g_{j_{1}}, h_{j_{1}}) and hence also with s_{1}, as the target of the state s under (g_{j_{1}}, h_{j_{1}}). Hence δ_{i} is associated with s_{i} for each i, and in particular δ_{r−1} is associated with s_{r−1}.

The target of s_{r−1} under g_{j_{r}} is now defined to be the failure state by rule (a) if r > r′, by rule (b) if r = r′ and by rule (c) if r < r′.

Hence av and also w = avb is rejected by the automaton.

Now finally, suppose that w is a D-reducible word which is accepted by W, and suppose that w′ is a D-reduction of w. Since w is accepted, H cannot carry a reduction for w. So, since w′ is a D-reduction of w, and H is sufficient, H must carry a reduction for w′. Hence w′ is rejected by W. □

Remarks

1. The procedure has been described in its most basic form. For an efficient implementation, improvements are necessary. A substantial improvement can be obtained if we can define a partial order of difference histories, for which, if δ′ = (d_{v,u′}, f(v, u′)) precedes δ = (d_{v,u}, f(v, u), then whenever va is minimally D-reducible and H carries a reduction of va to ub, H also carries a reduction of va to some u′b′. Given such a partial order, the procedure can be modified so that a difference history δ is discarded (that is, not included in the set of such associated with a state of the word acceptor) if there is another difference history δ′, preceding it in the order, which is also associated with that state.

2. If D were not substring closed, or H were not sufficient, then the procedure would certainly terminate, but with a word acceptor which might accept a pair of D-fellow travellers w, w′ representing the same group element. If this were the case, it would be recognised during the construction of the multipliers (that is, during step 4 of the full procedure). Hence, in some cases, in order to restrict the size of the computation, it might be appropriate to work with D and H for which the conditions of substring closure and sufficiency are not clearly satisfied.

5 f and H for various word orders

In this section, appropriate f and H are described for the wtlex, and wtshortlex orders and the wreath product order over shortlex. In each case the sufficiency of H is proved. The results of implementations of the procedure for each of these orders are discussed in section 6.

The following technical lemma will be useful for proving the sufficiency of some sets of difference histories. We state it in a rather general form so that we can apply it to each of the word orders considered in this paper.

Lemma 5.1 Suppose that ⪯ is a word order, and that μ is an additive positive valued function on words which is compatible with ⪯ (that is, such that μ(u) ≤ μ(v) whenever u ⪯ v, and μ(v_{1}v_{2}) = μ(v_{1}) + μ(v_{2})). Suppose that D is an inverse closed and substring closed difference machine. Let w_{1}, w_{2} be words which D-fellow travel, and let d = d_{w_{1},w_{2}} be the target word difference of (w_{1}, w_{2}). Then if w_{2} is D-irreducible, and no longer than w_{1},

μ(w_{2}) − μ(w_{1}) ≤ μ(d)

Proof: Since w_{2} is no longer than w_{1} and D is substring closed, w_{1}d and w_{2} fellow travel. If μ(w_{2}) − μ(w_{1}) > μ(d), then

μ(w_{1}d) = μ(w_{1}) + μ(d) < μ(w_{2}),

and so w_{1}d is a D-reduction of w_{2}, contradicting the fact that w_{2} is D-irreducible. □

5.1 The wtlex word order

Now, suppose that ⪯ is the wtlex word order. The order is defined by the rule that u ≺ v if wt(u) < wt(v), or if wt(u) = wt(v) and u precedes v lexicographically.

We can define a history function f, on pairs (v, u) of distinct words with l(v) ≥ l(u), as follows:-

f(v, u) = (len, lex, wtd)

where

len = 1 if l(v) > l(u) and len = 0 if l(v) = l(u);
lex = 1 if u precedes v lexicographically, otherwise lex = −1;
wtd = wt(v) − wt(u) if l(v) = l(u), otherwise wtd = min{wt(v) − wt(u), 1}.

It is left to the reader to verify that f has the appropriate properties.

Proposition 5.2 Let H be the set of all difference histories (d, (len, lex, wtd)) such that

−wt(d) ≤ wtd ≤ max_{d′∈D}wt(d′)

Then H is sufficient.

Proof: Suppose that v is minimally D-reducible, and suppose that u is any reduction of v. Let v(i) be any proper prefix of v. Then l(v(i)) = i ≥ l(u(i)). If l(u(i)) = i, then we can apply lemma 5.1 with w_{1} = u(i) and w_{2} = v(i) and the word difference d_{u(i),v(i)} to get

wt(v(i)) − wt(u(i)) ≤ wt(d_{u(i),v(i)}) ≤ max_{d′∈D}wt(d′)

If l(u(i)) < i, then the last component of f(v(i), u(i)) is defined to be at most 1.

Now first suppose that v is directly D-reducible. In that case let u be a Dreduction of v which is D-irreducible. Applying lemma 5.1 with w_{1} = v(i), w_{2} = u(i) and the word difference d_{v(i),u(i)} we see that

wt(v(i)) − wt(u(i)) ≥ −wt(d_{v(i),u(i)}).

So (d_{v(i),u(i)}, f(v(i), u(i))) is a difference history in H. Hence in this case H carries a reduction for v.

Now suppose that H does not carry a reduction for v. In this case the above argument shows that v cannot be directly D-reducible. Now suppose that u is a direct D-reduction for v, and let v′ be the shortest prefix of v for which, where i = l(v′), u′ = u(i) and d = d_{v′,u′}, the difference history (d, f(v′, u′)) is not in H. Then wt(v′) − wt(u′) < −wt(d), so wt(v′d) < wt(u′), and thus v′d ≺ u′. Since D is substring closed, v′d and u′ must D-fellow travel, so v′d is a D-reduction of u′, which is no shorter than u′. For any proper prefix u′′ = u′(j) of u′, v′′ = v′(j) is a proper prefix of v′, and so is certainly irreducible, so the difference history (d_{u′′,v′′}, f(u′′, v′′)) must be in H by lemma 5.1. Hence H carries a reduction for u. □

5.2 The wtshortlex word order

Now, suppose that ⪯ is the wtshortlex word order. The order is defined by the rule that u ≺ v if wt(u) < wt(v), or if wt(u) = wt(v) and u precedes v in shortlex

We can define a history function f almost exactly the same as for wtlex

f(v, u) = (len, lex, wtd)

where

len = 1 if l(v) > l(u) and len = 0 if l(v) = l(u);
lex = 1 if l(v) = l(u) and u precedes v lexicographically,
lex = −1 if l(v) = l(u) and v precedes u lexicographically, otherwise lex = 0
wtd = wt(v) − wt(u) if l(v) = l(u), otherwise wtd = min{wt(v) − wt(u), 1}.

We define a sufficient set H just as for wtlex.

5.3 Wreath product orders

For a wreath product order, each generator or inverse of a generator is assigned a level. The level, λ(v) of a word v is defined to be the maximum of the levels of all generators in it. Then, for any j, pfx_{n}(v) is defined to be the maximal prefix of v consisting only of symbols of weight at most j,and π_{j}(v) is defined to be the projection of pfx_{j}(v) onto its weight j symbols (that is the word formed by deleting from pfx_{j}(v) all symbols of weight other than j).

For a pair of words v, u with no common prefix, the wreath product ⪯ over an order ord is then defined (recursively) by the following rule:-

u ≺ v ⟺  either λ(u) < λ(v),
or λ(u) = λ(v) = J, and π_{J}(u) <_{ord} π_{J}(v),

or λ(u) = λ(v) = J, π_{J}(u) = π_{J}(v), and pfx_{J−1}(u) ≺ pfx_{J−1}(v).

Further, for any word a, au ≺ av if u ≺ v.

Suppose that ⪯ is a wreath product order, over ord, with levels from 1 … N. Suppose that g is a history function for ord. Then a little thought should show that the following defines a history function f for ⪯.

Let J = max{λ(v), λ(u)}. Then, for distinct v, u with l(v) ≥ l(u) and no common prefix, define

f(v, u) = (len, λ(v), λ(u), c_{1}, …, c_{J−1}, c_{J}),

where len = 1 if l(v) > l(u), = 0 if l(v) = l(u),
and for each  j ≤ J,
c_{j} = 1 if π_{j}(u) <_{ord} π_{j}(v) and (l(u) < l(v) or λ(u) > j);
c_{j} = −1 if π_{j}(v) <_{ord} π_{j}(u) and λ(v) > j;
c_{j} = 0 if π_{j}(v) = π_{j}(u);
otherwise c_{j} = (g(v_{j,1}, u_{j,1}), v_{j,2}, u_{j,2}),

where π_{j}(v) = v_{j,1}v_{j,2}, π_{j}(u) = u_{j,1}u_{j,2}, l(v_{j,1}) = l(u_{j,1})

and either u_{j,2} or v_{j,2} is trivial.

Further define f(av, au) = f(v, u), for any word a.

To verify the sufficiency of a particular set of difference histories, the following lemma is useful. We state it in some generality, since, although we only apply it to wreath products over shortlex, it might also be used for wreath products over weighted orders; then we deduce the result we need for the wreath product over shortlex as a corollary.

Lemma 5.3 Suppose that ⪯ is a wreath product order over ord, for which any generator and its inverse have the same level. Suppose that μ is an additive positive valued function on words which is compatible with ord. Let D be a difference machine, which is inverse closed, substring closed, and minimally labelled with respect to D. Let w_{1}, w_{2} be words which D-fellow travel, and let d = d_{w_{1},w_{2}} be the target word difference of (w_{1}, w_{2}). Then if w_{2} is D-irreducible, and no longer than w_{1}, and if J is the maximal level of a generator in either w_{1} or w_{2},

μ(π_{J}(w_{2})) − μ(π_{J}(w_{1})) ≤ μ(π_{J}(d))

Proof: Since a generator and its inverse must have the same level, the word w_{1}^{−1}w_{2} has level at most J, and hence, since D is minimally labelled, so does d_{w_{1},w_{2}}. Now, provided we restrict consideration to words of level at most J, the composite function μ ∘ π_{J} is compatible with ⪯. So we can apply lemma 5.1 to get the result. □

Corollary 5.4 Suppose that ⪯ is a wreath product order over shortlex, for which any generator and its inverse have the same level. Let D be a difference machine, which is inverse closed, substring closed, and minimally labelled with respect to D. Let w_{1}, w_{2} be words which D-fellow travel, and let d = d_{w_{1},w_{2}} be the target word difference of (w_{1}, w_{2}). Then if w_{2} is D-irreducible, and no longer than w_{1}, and if J is the maximal level of a generator in either w_{1} or w_{2},

l(π_{J}(w_{2})) − l(π_{J}(w_{1})) ≤ l(π_{J}(d))

We are now in a position to describe and verify a finite, sufficient set of difference histories for a wreath product order over shortlex.

Proposition 5.5 Suppose that ⪯ is a wreath product order over shortlex, for which any generator and its inverse have the same level. Let D be a difference machine, which is inverse closed, substring closed, and minimally labelled with respect to D. Let K be the maximal number of generators of any weight in a word difference. Then the set of difference histories H of the form

(len, λ(v), λ(u), c_{1}, …, c_{J−1}, c_{J}),

as described above, such that, for each j, c_{j} = 0, 1, −1 or (g(v_{j,1}, u_{j,1}), v_{j,2}, u_{j,2}), where v_{j,2} and u_{j,2} both have weight at most K, is sufficient.

Proof: NB. We shall use x <_{sl} y to indicate that x precedes y in shortlex.

The proof is analogous to the proof of proposition 4.5

Suppose that v is minimally D-reducible, and that u is any reduction of v. Without loss of generality we may assume that v and u have no common prefix. Let v′ = v(i) be a proper prefix of v, and u′ = u(i) the corresponding prefix of u. Let J be the maximum of the levels of v′ and u′, and let

δ = (len, λ_{v′}, λ_{u′}, c_{1}, …, c_{J−1}, c_{J})

be the difference history for (v′, u′). Note that for any j ≤ J, if c_{j} ∉ {0, 1, −1}, then either λ_{u′} ≤ j, l(u′) = l(v′) and π_{j}(u′) <_{sl} π_{j}(v′), or λ_{v′} ≤ j and π_{j}(v′) <_{sl} π_{j}(v′).

Suppose first that u′ is shorter than v′, and that c_{j} ∉ {0, 1, −1}. Then π_{j}(v′) <_{sl} π_{j}(u′), so v′_{j,2} is trivial. Suppose on the other hand that u′ has the same length as v′. Then we can apply corollary 5.4 with w_{1} = u′ and w_{2} = v′ to see that

l(π_{J}(v′)) − l(π_{J}(u′)) ≤ K,

and hence that v′_{J,2} has length at most K. Further, if j < J, where we define m_{j} to be the largest integer such that neither v(m_{j}) nor u(m_{j}) contains a generator of weight greater than j, we can apply corollary 5.4 to the words u(m_{j}) and v(m_{j}) to see that

l(π_{j}(v(m_{j}))) − l(π_{j}(u(m_{j}))) ≤ K,

and hence that v′_{j,2} has length at most K. (For if v_{j,2} is non-trivial, it is a suffix of π_{j}(v′(m_{j})) of length at most l(π_{j}(v(m_{j})))−l(π_{j}(u(m_{j}))). Hence we see that, for any u, if c_{j} ∉ {0, 1, −1}, then l(v′_{j,2}) ≤ K.

Now suppose that v is directly D-reducible, and that u is a D-reduction of it which is D-irreducible. Then u′ is D-irreducible, and so we can apply corollary 5.4 to u′ and v′ to get

l(π_{J}(u′)) − l(π_{J}(v′)) ≤ K,

and hence deduce that if c_{J} ∉ {0, 1, −1} then u′_{J,2} has length at most K. Similarly, for any j < J, applying corollary 5.4 to u(m_{j}) and v(m_{j}) we get

l(π_{j}(u(m_{j}))) − l(π_{j}(v(m_{j}))) ≤ K,

and hence deduce that if c_{j} ∉ {0, 1, −1} then u′_{j,2} has length at most K. Hence δ is in H, and so H carries a reduction for v.

So now suppose that H does not carry a reduction for v. Then v cannot be directly D-reducible. Choose i minimally so that where v′ = v(i) and u′ = u(i), the associated difference history δ is not in H.

For each j < J, a word of length |l(π_{j}(v(m_{j}))) − l(π_{j}(u(m_{j})))| is one of the components of the difference history for (v′(m_{j}), u′(m_{j})). So (by the minimality of i), certainly |l(π_{j}(v(m_{j}))) − l(π_{j}(u(m_{j})))| ≤ K, and so l(u_{j,2}) ≤ K for j < J. Hence, since δ ∉ H, u_{J,2} has length greater than K, that is

|l(π_{J}(u′)) − l(π_{j}(v′))| > K ≥ l(π_{J}(d_{v′,u′}))

Now, where d = d_{v′,u′},

l(π_{J}(v′d)) ≤ l(π_{J}(v′)) + l(π_{J}(d)) < l(π_{J}(u′))

So v′d ≺ u′. Since v′ is no shorter than u′ and D is prefix closed, v′d and u′ must D-fellow travel. Hence v′d is a direct D-reduction of u′. Thus u′ is directly D-reducible, and so H must carry a reduction for u′, and also for u. □

6 Examples

6.1 Weighted orders

The original motivation to extend these algorithms came from Epstein’s result ([6]) for geometrical finite hyperbolic groups; Lang’s recent result ([14]) now shows that such groups are in fact shortlex automatic, but it still seemed of interest to examine Epstein’s automatic structures. Experiments described below with some hyperbolic knot groups produced automatic structures which verified Epstein’s result, but the results were a little disappointing in that the structures were larger than other shortlex structures.

Epstein’s result suggests that a wtlex automatic structure can be found for the fundamental group of a geometrically finite hyperbolic manifold by associating weights to the generators in such a way that low weights are assigned to generators corresponding to paths around cusps of the manifold. In a private communication, Epstein suggested that an automatic structure for a hyperbolic knot groups should therefore be found by adjoining to the generators of the Wirtinger presentation (as defined in, for example [8]) one additional generator corresponding to a path around the knot, giving that generator and one other weight one, and all the others the same, possibly higher, weight.

Three hyperbolic knots were investigated, those labelled as 4_{1}, 5_{2} and 7_{4} in the table of [21] (and proved hyperbolic in [19, 20]); 4_{1} is commonly known as the figure 8 knot. With respect to the Wirtinger generators, all three were easily proved to be shortlex automatic. The word acceptors had 18, 21 and 31 states, and the difference machines D_{L} 21, 29 and 43 states respectively.

With the addition of an extra generator a representing a path around the knot, presentations

⟨a, x, y, z, t | a^{−1}xy^{−1}zt^{−1}, x^{−1}z^{−1}tz, y^{−1}txt^{−1}, z^{−1}x^{−1}yx⟩
⟨a, x, y, z, t, u | a^{−1}tuxzy, xt^{−1}x^{−1}z, ty^{−1}t^{−1}x, tzu^{−1}z^{−1}, uz^{−1}u^{−1}y⟩
⟨a, x, y, z, t, u, v, w | a^{−1}vu^{−1}x^{−1}w^{−1}y^{−1}z^{−1}t^{−1}, t^{−1}xzx^{−1}, xvy^{−1}v^{−1},
yuy^{−1}v, uyu^{−1}z^{−1}, wtw^{−1}u^{−1}, twt^{−1}x^{−1}⟩

were deduced for the three knot groups from their Wirtinger presentations. In each case, the group proved in fact to be shortlex automatic on the larger set of generators, with the generators ordered with a first, and then x, y, z, t …; of course this is the special case of the wtlex order where all generators have weight 1. The automatic structures were much larger than those found using just the Wirtinger generators. The word acceptors had 781, 265 and 523 states, and the difference machines D_{L} 287, 383 and 647 states respectively. The computation was also significantly larger; the latter two calculations in particular took 2500 seconds and 6300 seconds on a SUN Sparc 20workstation with 256 MByte RAM. (This calculation was actually done with the existing kbmag software for shortlex, which is, of course, intrinsically more efficient than the more general algorithm for wtlex).)

For each of the three groups, experimentation with Knuth-Bendix on wtlex, with weight 1 assigned to a and x and equal weights from 2 through to 10 assigned to remaining generators, produced no evidence of stablility in the number of word differences coming from the associated rewrite system.

Certain Coxeter groups with non-standard generating sets (that is, with additional involutions introduced) were proved by Hermiller in [11] to have finite rewriting systems with respect to wtlex. A number of examples of this type were investigated using the algorithm described in this paper and found to be wtlex automatic, wtshortlex automatic and shortlex automatic, for those generating sets. In all cases investigated, the wtlex language was the simplest of the three languages for that generating set (that is, the word acceptor had fewer states), but the shortlex language for the standard generating set was simpler than that.

6.2 Wreath product over shortlex

In this section four infinite classes of groups are described, all of which are either automatic or asynchronously automatic (in the latter case only a more general fellow traveller property is required, see [6] for a full definition) with respect to a wreath product order over shortlex. At least for small values of the parameters p, q, the algorithm described in this paper can be used to verify automaticity where relevant; but in each case a combinatorial proof is also straightforward to obtain.

For p, q > 0, the Baumslag-Solitar group G_{p}, q is defined by the presentation

G_{p,q} = ⟨x, y | yx^{p} = x^{q}y⟩

Where x, x^{−1} have level 1, and y, y^{−1} have level 2, G_{p,q} has finite rewriting system:-

xx^{−1} → 1, x^{−1}x → 1, yy^{−1} → 1, y^{−1}y → 1,
x^{r+1}y^{−1} → x^{r+1−p}y^{−1}x^{q}, x^{r−p}y^{−1} → x^{r}y^{−1}x^{−q}, r = ⌊p/2⌋
x^{s+1}y → x^{s+1−q}yx^{p}, x^{s−q}y → x^{s}yx^{−p}, s = ⌊q/2⌋.

The minimal representatives of group elements under that order define the regular language of words of the form

y^{a}x^{b_{1}}y^{c_{1}} … x^{b_{k}}y^{c_{k}}x^{d}

where a, k, d ∈ Z, k ≥ 0, and for each i ≤ k, either c_{i} > 0 and b_{i} ∈ {1, … s, −1, …, s + 1 − q}, or c_{i} < 0 and b_{i} ∈ {1, … r, −1, …, r + 1 − p}. This is recognised by an automaton with max{p, q} + 4 states.

When p = q the language satisfies the fellow traveller property, so we have an automatic structure. For particular values of p, q this can easily be verified using the algorithm described in this paper. However, a combinatorial argument, examining the relationship between pairs of accepted words (v, u) such that u = vy, provides a brief, alternative proof, covering all p, q ≥ 0.

The same argument shows that when p ≠ q, the language satisfies an asynchronous fellow traveller property, that is, for v, w ∈ L with w =_{G} vy, and w = zw′, v = zv′, travellers on v′ keep close to travellers on w′, provided that they move at appropriate speeds (in fact, with speeds which, except at the beginning, and depending on v′ and w′, stay in the ratio p : q or q : p). The algorithm fails to verify a synchronous fellow traveller property; in fact no such is satisfied.

In fact, in [6], Chapter 7, G_{p,q} is proved to be automatic for p = q, and asynchronously automatic (but \underline{not} automatic) for p ≠ q. For p ≠ q, G_{p,q} cannot be automatic, because it has an exponential Dehn function.

Although this fact is not mentioned in [6], the language of that proof can be recognised as the set of minimal representatives of group elements under a wreath product over lex. G_{p,q} also has a finite rewriting system with respect to that order; the language of minimal representatives is very similar to the above, and the same fellow traveller properties can be similarly verified. But this order is less appropriate for computation; it admits infinite descending chains, and so is not a reduction order.

Calculation proves that G_{p,p} is also shortlex automatic (at least for small p); but wreath product orders give a much simpler language.

For p, q > 0, the group G_{p,−q}, defined by

G_{p,−q} = ⟨x, y | yx^{p} = yx^{−q}⟩ p, q, > 0

also has a finite rewriting system:-

xx^{−1} → 1, x^{−1}x → 1, yy^{−1} → 1, y^{−1}y → 1,
x^{r+1}y^{−1} → x^{r+1−p}y^{−1}x^{−q}, x^{r−p}y^{−1} → x^{r}y^{−1}x^{q}, r = ⌊p/2⌋
x^{s+1}y → x^{s+1−q}yx^{−p}, x^{s−q}y → x^{s}yx^{p}, s = ⌊q/2⌋

The same language as for G_{p,q} gives an automatic structure for p = q; the algorithm verifies this easily. A combinatorial argument provides a brief, alternative proof, that G_{p,−p} is automatic for all p > 0 and that G_{p,−q} is asynchnously automatic for p, q > 0 and p ≠ q.

Again, computation shows G_{p,−p} is shortlex automatic at least for small p, but the language is much more complicated than that provided by the wreath product order.

For p, q > 0 the group H_{p,q} defined by

H_{p,q} = ⟨x, y | x^{p}y = y^{−1}x^{q}⟩ p, q, > 0

has a finite rewriting system

xx^{−1} → 1, x^{−1}x → 1, y^{−1} → x^{p}yx^{−q}, yx^{p}y → x^{q},
x^{t+1}y → x^{t+1−(p+q)}yx^{p+q}, x^{t−(p+q)}y → x^{t}yx^{−(p+q)}, t = ⌊(p + q)/2⌋.

The minimal representatives of group elements under that order define the regular language of words of the form

x^{a_{1}}y^{b_{1}} … x^{a_{k}}y^{b_{k}}x^{c}

where a, k, d ∈ Z, k ≥ 0, for each i ≤ k, b_{i} > 0, a_{1} < p, and for 1 < i ≤ k,

a_{i} ∈ {1, …, t, −1, …, −(p + q) + t + 1}

The fellow traveller property holds for all p, q; this can easily be verified combinatorially, and essentially follows from the relation

x^{p+q}y = yx^{p+q}

(which shows that H_{p,q} is a quotient of G_{p+q,p+q}.) So H_{p,q} is automatic for all p, q.

For p, q > 0 the group H_{p,−q} defined by the presentation

H_{p,−q} = ⟨x, y | x^{p}y = y^{−1}x^{−q}⟩ p, q, > 0

has finite rewriting system

xx^{−1} → 1, x^{−1}x → 1, y^{−1} → x^{p}yx^{q}, yx^{p}y → x^{−q}.

The minimal representatives of that order define the regular language of words of the form

x^{a_{1}}y^{b_{1}} … x^{a_{k}}y^{b_{k}}x^{c}

where a, k, d ∈ Z, k ≥ 0 for each i ≤ k, b_{i} > 0, a_{1} < p, and for 1 < i ≤ k, a_{i} ≠ p.

The fellow traveller property holds for all p, q. This can very easily be verified combinatorially; if u, v ∈ L, and l(v^{−1}u) ≤ 1, then the words u, v must be of the form wu_{0}, wv_{0} for short words v_{0}, u_{0}. So in fact, the language is a broomlike combing, in the sense of [1]; hence by [1] this group is virtually free.

References

[1] Martin R. Bridson and Robert H. Gilman, A remark about combings of groups, Internat. J. Algebra Comput. 3 (1993),575–581.

[2] Brigitte Brink and Robert Howlett, A finiteness property of Coxeter groups, Math. Ann., 296 (1993), 179–190.

[3] J. W. Cannon,The combinatorial structure of cocompact discrete hyperbolic groups, Geom. Dedicata 16 (1984), 123–148.

[4] Ruth Charney, Artin groups are biautomatic, Math. Ann. 292 (1992), 671– 683.

[5] Ruth Charney, Geodesic automation and growth functions of Artin groups, Math. Ann. 301 (1995), 307–324.

[6] David B. A. Epstein J.W. Cannon, D. F. Holt, S. Levy, M. S. Patterson and W. Thurston,Word processing in groups, Jones and Bartlett, 1992.

[7] D.B.A. Epstein, D.F. Holt and S.E. Rees, The use of Knuth-Bendix methods to solve the word problem in automatic groups, J. Symb. Comp. 12 (1991), 397–414.

[8] Richard H. Crowell and Ralph H. Fox, Introduction to knot theory, Blaisdell Publishing Co., New York, Toronto, London, 1963.

[9] S.M. Gersten and H.B. Short, Small cancellation theory and automatic groups, Inv. Math. 102 (1990) 305–334.

[10] R. H. Gilman, Presentations of groups and monoids, J. Alg. 57 (1979) 544–554.

[11] Susan M. Hermiller, Rewriting systems for Coxeter groups, J. Pure Appl. Alg. 92 (1994), 137–148.

[12] Derek F. Holt, The Warwick automatic groups software, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 25 (1996), 69–82.

[13] Arye Juhasz, Technion, Haifa, private communication.

[14] U. Lang,Quasigeodesics outside horoballs, Geo. Ded. , 63 (1996), 205–215.

[15] Gilbert Baumslag et al., Magnus system for computational group theory, New York Group Theory Cooperative, CCNY, New York.

[16] Lee Mosher, Mapping class groups are automatic, Ann. Math., 142 (1995), 303–384.

[17] P. Papasoglu, Strongly geodesically automatic groups are hyperbolic, Inv. Math., 121 (1995), 323–334.

[18] David Peifer, Artin groups of extra-large type are automatic, J. Pure Appl. Alg. 110 (1996), 15–56.

[19] Robert Riley, A quadratic parabolic group, Math. Proc. Cam. Phil. Soc., 77 (1975), 281–288.

[20] Robert Riley, Parabolic representations of link groups, Mathematika 22 (1975), 141–150.

[21] Dale Rolfsen, Knots and Links, Publish or Perish, Berkeley, 1976.

[22] M. Schönert et. al., GAP - Groups, Algorithms and Programming, Lehrstuhl D für Mathematik, RWTH Aachen, Germany, 1994.

[23] C.C. Sims, Rutgers Knuth-Bendix Program, Rutgers University, New Jersey, available by anonoymous ftp from dimacs.rutgers.edu/pub/rkbp.

[24] Paul Wakefield, Procedures for automatic groups, PhD, University of Newcastle, 1998.