{'fraction_non_alphanumeric': 0.04671587020162454, 'fraction_numerical': 0.007194986187275801, 'mean_word_length': 3.727777777777778, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A language theoretic analysis of combings

A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This paper gives a systematic analysis of the properties of groups with combings in various formal language classes, and of the closure properties of the associated classes of groups. It generalises previous work, in particular of Epstein et al. and Bridson and Gilman.


Introduction
The concept of a combing for a finitely generated group has grown out of the definition of an automatic group (as introduced in [10]); in the terminology of this paper, a group is automatic precisely when it possesses a regular synchronous combing. (Roughly speaking, a combing is an orderly set of strands through a Cayley graph of the group, which is regular if it is defined by a finite state automaton; a formal definition is given in section 2.) The class of automatic groups has valuable properties (particularly from a computational point of view) and contains a wealth of examples. However it is disappointing for its failure to include the fundamental groups of all compact geometrisable 3-manifolds, particularly so since it was the properties of the fundamental groups of compact hyperbolic manifolds observed in work of Cannon ( [9]) which motivated the definition of this class; subsequent work in [10] The author would like to thank both the Fakultät für Mathematik of the Universität Bielefeld for its hospitality while this work was carried out, and the Deutscher Akademischer Austauschdienst for its financial support. then showed that the fundamental groups of compact 3-manifolds modelled on 6 of Thurston's 8 geometries are in fact automatic. Further, no nilpotent group without a finite index abelian subgroup is automatic, and no soluble (non virtually abelian) example is known (at least to this author).
A result of Bridson and Gilman ([7]) suggests a way to remedy the deficiencies of automatic groups. Bridson and Gilman show that the fundamental group of any compact geometrisable 3-manifold possesses an asynchronous combing which is an indexed language (as defined in [1]); the same techniques show that the same result holds for many nilpotent and soluble groups. The class of groups with combings of this type is defined by weakening both of the two restrictions on the 'language' associated with an automatic group; the geometric 'fellow traveller condition' is relaxed from a synchronous to an asynchronous condition, and the language theoretic requirement of regularity is replaced by the requirement that the language be indexed (that is, recognised by a one-way nested stack automaton, a type of machine, defined in [2], which is a little more general than a pushdown automaton).
Most of the recent more general results on combings have concentrated on those which, as in Bridson and Gilman's case, are asynchronous; these are certainly easier to find than synchronous combings. However, from a practical point of view, synchronous combings, when they exist, are more useful. The value of the study of these is increased by a very recent, and as yet unpublished, result of Bridson and N. Brady, which constructs a synchronous combing for a group which is not biautomatic, and almost certainly not automatic.
Naturally some properties of the class of automatic groups are lost by the move to a more general definition; however, widening the definition admits more constructions within a class of combable groups, and so allows more examples. Our aim in this paper is to give a systematic analysis of the properties of various classes of synchronous and asynchronous combings defined by formal language classes, to see to what extent properties of the class of automatic groups still hold in these classes, and what further properties can be deduced. We build on results in [10], [7], [5] and [20], in particular the first two of those. Often the proofs of these papers remain valid with a small amount of adjustment in the more general context we need; details from the original proofs are sometimes repeated for greater clarity. Our goal is to prove these results in the most general context possible. Section 2 of this article contains the definitions of various types of combings and fellow traveller properties; section 3 introduces the formal language theory which is used. Section 4 examines the solubility of the word problem, section 5 the closure of classes of combings under change of generators and various finite variations. Section 6 looks at the closure of combing classes under free and direct products, central and split extensions, and finally section 7 uses a result of Bridson, already used by Bridson and Gilman to find indexed combings for fundamental groups of N il and Sol manifolds, to show that similar combings exist also for many other nilpotent and soluble groups (this question is examined in more detail in [13]).

Fellow traveller properties, languages and combings
Let G be a group, with identity element e, and finite generating set X. Without loss of generality, we may assume that X is inverse closed, that is, contains the inverse of each of its elements; we shall make this assumption thoughout this paper. We call a product of elements in X a word over X, and denote by X * the set of all such words. Let Γ = Γ G,X be the Cayley graph for G over X, with vertices corresponding to the elements of G, and, for each x ∈ X, a directed edge from the vertex g to the vertex gx, labelled by x. Let d G,X measure (graph theoretical) distance between vertices of Γ G,X . For words w, v ∈ X * , we write w = v if w and v are identical as words, w = G v if w and v represent the same element of G. We define l(w) to be the length of w as a string, and l G (w) to be the length of the shortest word v with v = G w. It is straightforward to extend d G,X to a differentiable metric on the 1-skeleton of Γ. Then each word w can be associated with a differentiable path from e labelled by w such that, for t < l(w), the path from e to w(t) has length t, and for t ≥ l(w), w(t) = w(l(w)).
Suppose that v, w are words in X * , and that K ∈ N. Various fellow traveller properties can describe the relationship between v and w. We say that v and w synchronously K-fellow travel if for all t, d G,X (v(t), w(t)) ≤ K. More generally, we say that v and w asynchronously K-fellow travel if there is a strictly increasing, differentiable function h : R → R, mapping [0, l(v)] onto [0, l(w)], with the property that, for all t > 0, d G,X (v(t), w(h(t))) ≤ K. We say that v and w asynchronously K-fellow travel with bound M , if for all t ≤ l(v), the function h above satisfies 1/M ≤ h ′ (t) ≤ M . We shall call h the relative speed function of v and w, and K the fellow traveller constant. Note that v and w synchronously fellow travel if and only if they asynchronously fellow travel with relative speed function h defined by h(t) = t.
We define a language for G over X to be a set of words in X which contains at least one representative for each element of G. A language is bijective if it contains exactly one representative of each group element, prefix closed if it contains every prefix of each of its elements. It is geodesic if for each w ∈ L, l(w) = l G (w), and near geodesic if, for some constant ǫ, for all w ∈ L, l(w) − l G (w) < ǫ (this is stronger than being quasigeodesic, see [10]).
Suppose that L is a language for G. We call L a synchronous combing if for some constant K (the fellow travelling constant for L), the K-fellow traveller condition is satisfied by all pairs of words v, w ∈ L for which w = G vx for some x ∈ X ∪ {e}. We call L a synchronous bicombing if the K-fellow traveller condition is also satisfied by pairs of words xv, w with v, w ∈ L and w = G xv, for x ∈ X. We call L an asynchronous combing if for some K the asynchronous K-fellow traveller condition is satisfied by all pairs of words v, w ∈ L for which w = G vx for some x ∈ X ∪ {e}, and an asynchronous bicombing if the same is true for words xv, w with v, w ∈ L and w = G xv, for x ∈ X. We say that an asynchronous combing (or bicombing) L is boundedly asynchronous if for some constant M , relevant pairs of words asynchronously fellow travel with bound M . (Boundedly asynchronous combings are important for the study of asynchronously automatic groups in [10].) When we state results, we need to be very clear about the various fellow traveller conditions which are currently under discussion. Hence we shall consider the words combing and bicombing to have a rather general meaning, when used without further qualification. We introduce the a notion of type of a combing for situations where we need to be more precise.
More specifically, we shall use the term combing for a language which is either a synchronous, asynchronous, or boundedly asynchronous combing or bicombing, and call a group combable if it has a combing. Similarly, we shall use the general term bicombing for a language which is either a synchronous, asynchronous, or boundedly asynchronous bicombing, and call a group bicombable if it has a combing. A type, τ , of combing will be one of the six classes of combings (asynchronous, boundedly asynchronous or synchronous combings or bicombings) we have defined above; we shall call the set of all six classes T , and for τ ∈ T , we shall say that a combing in the class τ has type τ . (Clearly a combing may therefore have more than one type.) The following inclusions between these classes are fairly clear:sync. combings ⊂ bdd. async. combings ⊂ async. combings ∪ ∪ ∪ sync. bicombings ⊂ bdd. async. bicombings ⊂ async. bicombings We call fellow traveller properties holding between pairs of words v, w with w = G v or w = G vx right fellow traveller properties, and fellow traveller properties holding between pairs of words v, w with w = G xv left fellow traveller properties.
We call a combing bijective, prefix closed, geodesic or near geodesic if the underlying language has those properties. Note that the literature contains various uses of the term combing; [10], for instance, requires that the language consist of quasigeodesics, and [5] and [7] require that the language be bijective. We prefer to use a more general definition. In fact, when we construct combings out of other combings, it will often be clear from the construction that properties such as bijectivity, prefix closure, geodesicity or near geodesicity possessed by the original combings would be inherited by the new ones; in general, however the construction itself is not dependent on those properties.
We have the following general results for combable groups, from [5] and [11]. (In fact both authors assumed bijectivity as part of their definition of a combing, but the condition was not used.) Proposition 2.1 ( [5]) Any asynchronously combable group is finitely presented.
Proposition 2.2 ( [11]) Any asynchronously combable group has an exponential isoperimetric inequality. A group with a prefix closed asynchronous combing has a quadratic isoperimetric inequality.
As an immediate corollary to proposition 2.2 (see, for instance [10], theorem 2.2.5) we have Corollary 2.3 Any asynchronously combable group has soluble word problem.
Hence, since finitely presented soluble groups of derived length 3 are known with insoluble word problem ( [19,4]), the following is obvious.
Corollary 2.4 There exist finitely presented soluble groups of derived length 3 which are not asynchronously combable.
A natural restriction to put on a combing is to require that it is a language in one of the families of formal languages, that is, a language recognised by some theoretical model of computation (or equivalently, defined by a formal grammar). The combing of an automatic group is required to be a regular language. Bridson and Gilman in [7] studied bijective, asynchronous combings in various formal language families, in particular the families of bounded languages, regular languages, context-free languages and indexed languages, and more generally any full abstract family of languages (of which the last three are examples, see [18] ). We aim to give a more general analysis, covering both a range of fellow traveller conditions (synchronous and even boundedly asynchronous conditions are in general harder to obtain than asynchronous ones) and a range of language families.

Families of languages
Following [18], we define a family of languages to be any non-empty set of languages over finite alphabets; hence in particular, we include under this definition the set U of all languages with finite alphabet. Of course, all the closure properties for a language family given as conditions for the results in the following sections are valid in U , and hence those results hold for combings for which there is no language theoretic restriction. However, in this paper, we are chiefly interested in combings associated with families of formal languages.
Many families of formal languages are described in [18], including the four families of the Chomsky Hierarchy (regular sets, context-free languages, contextsensitive languages and recursively enumerable sets), the recursive sets, and (briefly) the indexed languages; [14] provides a more detailed mathematical treatment of context-free languages. [12] provides a very useful introduction to formal language theory from a group theoretical standpoint. The indexed languages were originally defined, and are more fully described in [1] and [2]. Bounded languages are described in [16].
A formal language may be defined by a machine which recognises it; for example, regular sets are recognised by finite state automata, context-free languages by (non-deterministic) pushdown automata, recursively enumerable and recursive sets by Turing machines and halting Turing machines respectively. Alternatively, a formal language may be defined by a set of grammatical rules. Such a description may well be more digestible; certainly this seems to be the case for indexed languages, recognised by one way nested stack automata, and generated by grammars described in [1], and also in [7].
From now on, we shall use the symbol F to denote a family of languages, and in particular R to denote the family of regular sets, C the context-free languages, DC the deterministic subfamily of C, I the indexed languages, Rec the recursive sets and Ren the recursively enumerable sets. We call a combing for a group G an F-combing if it is a combing in the family F of languages. Of course, every combing is a U -combing.
Hopcroft and Ullman follow a general approach to the study of formal languages proposed by [15] and based on the closure properties of the various families. Recognising that some closure properties are consequences of others, they introduce the concepts of abstract and full abstract families of languages, and also of trios and full trios, for which various closure properties are satisfied. More precisely, where P ∩R etc. are as defined in table 1, a family of languages is called a trio if it satisfies P ∩R , P ǫ−f reeh and P h −1 , a full trio if it is a trio which also satisfies P h , an abstract family of languages (AFL) if it is a trio which also satisfies P ∪ , P • and P + , and a full AFL if it is a full trio which also satisfies P ∪ , P • and P * . The families R, C, I and Ren are full AFL's; Rec is an AFL ( [18,7]).
The properties of formal languages defined in table 1 are used in this paper (or seem to be of related interest). The results quoted are mostly taken from [18]; some results for indexed languages come from [1,2,17].

Recognising fellow travellers, bijectivity and the word problem
Where G is a group with finite generating set X, for any constant K, the set of pairs of words (w, v) in X * which synchronously K-fellow travel is a regular set. It is recognised by a (2-stringed) finite state automaton which is usually known as a difference machine D K ; the states of D K correspond to 'word differences' (that is, the words of length at most K which connect a pair of fellow travellers), Membership of a language in F is decidable. Implied by P ∅ ∧ P ∩R .
The intersection of a language in F with a regular set is in F.

Any trio.
P h The image of a language in F under a homomorphism (the restriction to the language of a semigroup homomorphism mapping ǫ to ǫ) is in F.

Any full trio.
P ǫ−f ree h The image of a language in F under a homomorphism h with h(a) = ǫ, ∀a = ǫ is in F.

Any trio.
P ǫ−bdd h (limited deletion) The image of a language in F under a homomorphism h for which h maps at most K consecutive symbols in any string of L to ǫ (for some constant K) is in F.
Any trio.
Any trio.

P GSM
The image of a language in F under the operation of a generalised sequential machine (GSM) mapping is in F. A generalised sequential machine is defined as in [18] to be a (possibly non-deterministic) finite state automaton with an attached output string. Corresponding to each transition of the underlying automaton is a (possibly trivial) word which is appended to the output string; when a word is accepted, the word currently on the output string is output. Implies in particular P h , P ∩R .
Any full trio.
P ǫ−f ree GSM The image of a language in F under the operation of an ǫ-free GSM mapping (for which there is nontrivial output on every transition) is in F. Implies in particular P ǫ−f ree h , P ∩R .
Any trio. and transitions encode the equations dx = G x ′ d ′ for word differences d, d ′ and x, x ′ ∈ X ∪ {e}. The target state of (w, v) corresponds to the word difference w −1 v, and hence D K can be used to recognise equality between pairs of words which synchronously K-fellow travel.
A difference machine D K can also be constructed from the word differences of an asynchronous combing. However the set of fellow travelling pairs of words is not recognisable simply as the language of D K as a finite state automaton; the pairs of words need to be fed asynchronously through the machine. Nonetheless, with appropriate usage of this machine, it is decidable whether or not two words w and v asynchronously K-fellow travel. Further, for any given word w, the set of words v which asynchronously K-fellow travel with w is regular, as is the subset of all such words v for which w −1 v is equal to any particular word difference.
Suppose that G has a synchronous combing L, with associated fellow traveller constant K. Let D K be the appropriate difference machine, and the shortlex word order (for which w v if w is shorter than v, or the same length as v and preceding it lexicographically). The subset R of L(D K ) consisting of pairs (w, v) with w v is then regular. If L is regular, then so is In this case, L 0 is a bijective, regular, synchronous combing for G. Hence every automatic group has a bijective, regular, synchronous combing.
The theoretical solubility of the word problem for an asynchronously combable group is, as we mentioned in section 2, an immediate consequence of Gersten's result that such a group has exponential isoperimetric inequality. When the combing L is recursively enumerable, just as in [10] for automatic groups, a practical solution to the word problem can be described, which is based on the Turing machine which recognises L, and the associated difference machine D K .
This algorithm to test that a given word v in the generators is trivial in the group G breaks down into three steps. The first step finds w e ∈ L, with w e = G e, the second finds w v ∈ L, with w v = G v, and the final step tests to see if w v = G w e . Given any w 0 = x 1 x 2 . . . x r ∈ L, w e can be found as the last word in a sequence of words w 0 , w 1 , . . . w r in L, such that w i+1 x r−i = G w i , and, where v = y 1 y 2 . . . y s , w v can be found as the last word in a sequence w r , w r+1 , . . . , w r+s , such that w r+i = G w r+i−1 y i ; thus the test is dependent on being able, given u ∈ L and x ∈ X, to find u ′ ∈ L, with u ′ = G ux. The set of all such u ′ is found as the intersection of L with the regular set of elements u ′ which both K-fellow travel with u and satisfy u ′ = G ux.
For automatic groups this algorithm is easily seen to be quadratic (in the size of the generating set). But the proof of this fact depends on the fact that the lengths of the words w i can be controlled. This is implied by the existence of 'multipliers' (which is in turn implied for automatic groups by the closure of the family of regular sets under intersection) and the pumping lemma for regular sets; hence in general we cannot expect such a bound on the complexity.

Finite variations and change of generators
In this section we examine how moving to a group related by some kind of finite variation to a given group G or changing the generating set for G affects combability.
The following technical lemma will be useful.
Lemma 5.1 Suppose that G is a group with finite generating sets X and Y , and that L is a language for G over X. Suppose that φ is a map from L into Y * , with the property that, for constants λ, C > 0, for any v ∈ L, Then any fellow traveller properties satisfied by L over X are satisfied by φ(L) over Y .
Proof: We start by fixing a set of words {w x : x ∈ X} over Y , such that w x = G x, and a set of words {w y : y ∈ Y } over X, such that w y = G y. Let M be the maximum length of any such w x or w y . Now suppose that v, w are two words in L, and φ(v), φ(w) their images in φ(L).
Suppose first that v and w asynchronously fellow travel over X, with relative speed function h, and fellow traveller constant K. Define H : R → R by λH(t) = h(λt). Then So φ(v) and φ(w) asynchronously fellow travel over Y with relative speed function H and fellow traveller constant 2C + M K.
Since h ′ = H ′ , we see that φ(v) and φ(w) boundedly asynchronously fellow travel over Y if and only if v and w do so over X. If h(t) = t for all t, then H(t) = t for all t, and so further, when v and w synchronously fellow travel, so do φ(v) and φ(w).
We verify separately that φ(L) inherits right and left fellow traveller properties from L.
To see that φ(L) inherits right fellow traveller conditions from L, suppose that v, w ∈ L and that φ(w) = G φ(v) or φ(w) = G φ(v)y, for some y ∈ Y . Then φ(v) = G vg, for some g ∈ G which has length at most C as a word over Y , and hence length at most M C as a word over X; similarly, for some g ′ , φ(w) = G wg ′ . So d G,X (v, w) < 2M C + 1, and so if L satisfies a right fellow traveller condition with fellow traveller constant K, v and w must fellow travel in the appropriate way at distance at most K(2M C + 1). The above then implies that φ(v) and φ(w) similarly fellow travel (with an appropriate constant). Now suppose that L satisfies both right and left fellow traveller conditions. We want to show that φ(L) then satisfies left fellow traveller conditions. Suppose that v, w ∈ L and that φ(w) = G yφ(v) for some y ∈ Y . Then φ(v) = G vg and φ(w) = G wg ′ , for g, g ′ as above, so yvg = G wg ′ . Then the right and left fellow traveller properties of L together imply that v and w fellow travel in the appropriate way at a distance of at most K(2M C + 1). Hence φ(v) and φ(w) similarly fellow travel. ✷ The results in the following proposition are mostly generalisations of results for automatic groups in [10]. Most of these results are also proved in a more general language theoretic setup (but not as general as ours) in [7] for asynchronous (but not synchronous) combings.  (b) Suppose that F is closed under concatenation with a finite set. Then if G has an aynchronous, boundedly asynchronous or synchronous F-combing so does any group J of which G is a subgroup of finite index.
(c) Suppose that F is closed under ǫ-free GSM mappings, and limited deletion.
Then if G has an F-combing L of type τ (i) G has an F-combing of type τ over any finite generating set, (ii) any subgroup H of finite index in G has an F-combing of type τ . If L is bijective then so is the combing for H.
Note that all the language theoretic conditions of this result are satisfied by R, C, I, Rec, Ren, and of course the family U of all languages with finite alphabet. Note also that part (b) of the result does not say anything about the bicombability of J. Proof: (a) Let ν represent the natural homomorphism from G to its quotient G/N . Let X = {x 1 , . . . , x n } be a generating set for G, and L an F-combing of type τ for G over X. Then the set X ′ = {x ν 1 , . . . x ν n } (in which no identifications are made between images of distinct elements of X which are equal in the quotient group) generates G/N . Define L ′ to be the set of images of elements of L under ν.
As a formal language L ′ is equivalent to L. It remains to verify the appropriate fellow traveller conditions. Hence suppose that v ν , w ν are elements of L ′ , where v, w ∈ L. To see that L ′ inherits the right fellow traveller properties of L, note that if w ν = G/N v ν , then w = G vn 1 for some element n 1 ∈ N , and if w ν = G/N v ν x ν i , then w = G vx i n 2 for some element n 2 ∈ N . Since N is finite, both n 1 and x i n 2 can be expressed as words over X of bounded length at most |N |. The fellow travel condition on L then implies that v and w fellow travel in the appropriate way at distance at most |N |K. To see that L ′ inherits the left fellow traveller properties of L, note that if w ν = G/N x ν j v ν , then w = G n 3 x j v, for some n 3 ∈ N , where n 3 x j can be written as a word of length at most |N | over X. Hence L ′ is a combing of the same type as L.
Now to prove the converse statement, suppose that Y is a generating set for G/N , and that now L ′ is an F-combing of type τ for G/N . Let Z be a set of elements of G which maps bijectively to Y under ν. Then Z ∪ N generates G. Choose L ′′ to be the natural set of words over Z which maps bijectively under ν to L ′ . L ′′ is equivalent to L ′ as a formal language. It is clear that the concatenation of L ′′ with N is a language in F for G over Z ∪ N . Now suppose that v = un and w = u ′ n ′ are two words in the language L ′′ N , with u, u ′ ∈ L ′′ , n, n ′ ∈ N . If w = G v, or w = G vn ′′ , for some n ′′ ∈ N , then u ν = G/N u ′ν . If w = G vz, for some z ∈ Z, then u ν y = G/N u ′ν , where y = z ν ∈ Y . Hence right fellow traveller properties of L ′ are inherited by L ′′ N .
Similarly if w = J n ′′ v, then u ν = G u ′ν , and if w = J zv, then y ν u ν = G u ′ν . Hence left fellow traveller properties of L ′ are inherited by L ′′ N .
(b) Let L be an F-combing for G over an alphabet X.
Let T be a set of left coset representatives for G in J. Certainly the concatenation L ′ of L with T is a language in F for J over X ∪ T . Now suppose that v = ut and w = u ′ t ′ are two words in that language, with u, u ′ ∈ L, t, t ′ ∈ T . If w = J v, then u = G u ′ . If w = J vy, for some y ∈ X ∪ T , then uu t,y = G u ′ , where u t,y ∈ L is a word representing a Schreier generator of G defined by the rule ty = G u t,y t t,y , for t t,y ∈ T and hence (since the set of such generators is finite) has bounded length as a word over X. Hence right fellow traveller properties of L are inherited by L ′ .
However left multiplication by elements of T is not controlled, and so left traveller properties of L are not clearly seen to be inherited by L ′ .
(c) (i) An asynchronous version of this result is proved in [7]; achieving a synchronous or boundedly asynchronous fellow traveller condition is harder. The argument is basically that of [10], but stated in more general language theoretic terms. First suppose that X is a generating set which does not contain the identity element. Then G has an F-combing over X if and only G has an F-combing over X ∪ {e}. One implication is obvious; a combing over X is also a combing over X ∪ {e}. On the other hand, given a combing L in F over X ∪ {e}, we construct (as in [10]) a language L ′ over X from L, by replacing (for some m > 0) every m-th occurrence of e in a word by a particular length m word w e , and deleting all other occurrences of e. L ′ is easily seen to be the image of L under a GSM mapping. Although this GSM mapping is not ǫ-free, we can find it as the composite of an ǫ-free GSM mapping (which replaces all but the m-th occurrences of e by some dummy symbol), and a homomorphism with limited deletion (of at most m − 1 consecutive symbols). Hence L ′ is in F. The conditions of lemma 5.1 are satisfied with λ = 1 and C = m; hence L ′ inherits the fellow traveller conditions of L. Now let X, Y be finite generating sets, and assume that G has an F-combing of type τ over X. By the above, we may without loss of generality assume that e ∈ Y . For each x ∈ X, we can find some word w x ∈ Y * which is equal to x in G. By appending copies of e where necessary, we can ensure that all the words w x have the same length m. A language L ′′ over Y is now defined as the image of L under the homomorphism which maps x to w x ;the condition P ǫ−f reeGSM implies P ǫ−f reehom , and so ensures that L ′′ is in F. The homomorphism expands the lengths both of words in L and their subwords in L by a constant factor m; hence lemma 5.1 applies. If only asynchronous fellow traveller properties are required, it is not essential for F to satisfy P ǫ−bdd , since padding with copies of the symbol e is no longer necessary; hence in this case it is sufficient for F to satisfy P ǫ−f reehom .
(ii) Now suppose that G has an F-combing L over a generating set X. Suppose that T is a right transversal for H in G, containing the identity. As above, the Schreier generators for H are defined to be all the products y tx = txt −1 tx , for x ∈ X, and t, t tx ∈ T , where t t,x is the representative in T of the coset containing tx. An ǫ-free generalised sequential machine M can be defined, which first rewrites any word x 1 . . . x k in G as a product y 1 . . . y k t, for Schreier generators y i and t ∈ T , by reading from left to right and applying a succession of rewrite rules of the form tx → y tx t tx , and then accepts x 1 . . . x k and outputs y 1 . . . y k in the case where t = G e, but otherwise rejects x 1 . . . x k . Let φ be the associated GSM mapping. Then where v = x 1 . . . x k and φ(v) = y 1 . . . y k , we see that d G,Y ∪T (φ(v)(i), v(i)) ≤ 1. Hence we can apply lemma 5.1 to see that φ(L) satisfies the same fellow traveller conditions over Y ∪ T that L satisfies over X. Since any word in φ(L) is in fact a word over Y , and word differences between such words are therefore elements of H, a little thought shows that φ(L) satisfies the same fellow traveller conditions over the subset Y of Y ∪ T . It is straightforward to see that if L is bijective then so is φ(L).

✷ 6 Products and extensions of combable groups
In this section we look at free and direct products, central extensions and (nearly) split extensions of F-combable groups, for F a class of formal languages. As in the previous section, all the language theoretic conditions of these results are satisfied by R, C, I, Rec, Ren, and of course the family U of all languages with finite alphabets.
The situation for free and direct products is quite straightforward. For central extensions, a result of Neumann and Reeves ( [20]) for biautomatic groups can be adapted for other language classes. Finally, a result of Bridson ([6]) deals with split extensions of combable groups over groups, such as abelian or word hyperbolic groups, which possess rather stable F-combings; Bridson's result is already rather general, but it seems worthwhile, since it is clearly a very useful result, to state and prove it here in the slightly more general form which is easily obtained. Proposition 6.1 (Free products) Let F be a family of languages, and τ one of the six classes of combings described in section 2.
Suppose that F is closed under concatenation, Kleene closure, and intersection with regular sets, and that G 1 and G 2 have F-combings of type τ , Then G 1 * G 2 has an F-combing of type τ , provided that if τ consists of synchronous combings, the combings for G 1 and G 2 are bijective.
Proof: Where L 1 and L 2 are the languages of G 1 and G 2 , over generator sets X 1 and X 2 , and L ′ 1 , L ′ 2 are the subsets of those which contain no non-trivial representatives of the identity, then L = (L ′ 1 L ′ 2 ) * is an appropriate language for G 1 * G 2 over X 1 ∪ X 2 .
The fellow traveller properties of L 1 and L 2 ensure that each contains at most finitely many non-trivial representatives of e, and hence L ′ 1 and L ′ 2 can be found as the intersections of L 1 and L 2 with regular sets, and are in F. Hence L ∈ F.
Aysnchronous fellow traveller properties are easily seen to be inherited by L from L 1 and L 2 ; for if two words w, w ′ in (L 1 L 2 ) * are related by an equation In the synchronous case, bijectivity ensures that for all but Essentially this proof is given in [3] for automatic groups; there bijectivity can be assumed. ✷ Proposition 6.2 (Direct products) Suppose that F is closed under concatenation, and that G 1 and G 2 have F-combings L 1 and L 2 . Then L 1 L 2 is an asynchronous F-combing for G 1 × G 2 , and an asynchronous bicombing if L 1 and L 2 are asynchronous bicombings. If L 1 and L 2 are bijective, then so is Where L 1 and L 2 are both synchronous or boundedly asynchronous then so is L 1 L 2 provided that L 1 is a near geodesic language.
Proof: The proof follows the argument of [10] for automatic groups, and uses the obvious decomposition of the Cayley graph for G 1 × G 2 (with respect to a sensible generating set) into Cayley graphs for G 1 and G 2 . The near geodesic condition ensures that, for generators x, y), the lengths of v and v ′ differ by a finite amount; for automatic groups, a language can always be found in which this condition holds. ✷ In fact this direct product result is a corollary of the asynchronous split extension result which is to come.
Neumann and Reeves' result on (virtually) central extensions of biautomatic groups of [20,21] can be generalised to central extensions of F-combable groups of various types without much difficulty. However it is not clear that the restrictive conditions will often be satisfied, for non-regular combings. Before we can state that result, we need some notation.
Let H be a group with a combing L and generating set X, and A a finitely generated abelian group, on which H acts as a group of automorphisms. An extension G of A by H is then specified by a section s : H → G for H in G, with s(e) = e, together with a cocycle σ : H × H → A, which satisfies the rule Group elements can be written as products of the form s(h)a, and the above rule, together with the action of H on A, defines multiplication between those products. The extension of A by H is central if H acts trivially on A.
σ is defined (as in [20]) to be an L-regular cocycle if (a) the sets σ(X, H) and σ(H, X) are finite, and (b) for each x ∈ X and a ∈ A, the set {v ∈ L : σ(v, x) = a} is regular.
Let H be a group with an F-combing L over a generating set X. Let G be a central extension of A by H, defined by a section s : H → G and a cocycle σ : H × H → A. Suppose that F is closed under GSM mappings and concatenation with a regular set. Suppose also that σ is L-regular. Then G has an asynchronous F-combing L ′′ . If L is a bicombing, then so is L ′′ .
If L is synchronous or boundedly asynchronous, then so is L ′ , provided that L is a near geodesic language.
Proof: The proof is basically that of Neumann and Reeves, translated into the appropriate language.
Define Y to be the set of all elements of G of the form y x,h = s(x)σ(h, x) −1 for h ∈ H, x ∈ X. The finiteness of σ(X, H) ensures that Y is finite. Let Z be a generating set for A, and L A a regular synchronous bicombing for A.
Hence s(w) is represented by the word Let L ′ be the set of all words of that form, and define L ′′ to be the language L ′ L A . Then L ′′ is clearly a language for G.
The fellow traveller properties of L ′′ can be seen to be inherited from L using arguments similar to those of [20], as follows.
First suppose that w, w ′ ∈ L and let w 0 , w ′ 0 ∈ L ′ represent s(w), s(w ′ ). Then for any t, w 0 (t), and w ′ 0 (t) are elements of L ′ representing s(w(t)) and s(w ′ (t)). Hence if w 0 = G w ′ 0 or w 0 = G w ′ 0 y for some y ∈ Y , right fellow traveller properties of L imply that w 0 and w ′ 0 fellow travel in the appropriate way. Left fellow traveller properties of L (if they exist) imply that w 0 and yw ′ 0 fellow travel For v, v ′ ∈ L A , fellow traveller properties between pairs of words w 0 v and [20], from the fellow traveller properties of L ′′ and L A separately. A condition that L is a near geodesic language ensures that the difference in lengths of v 0 and v ′ 0 remain bounded; for the automatic groups considered by [20] this property can always be assumed to hold.
It remains to show that L ′′ is in F. We show this by effectively translating the construction of [20] into language theoretic terms. Since F is closed under concatenation with a regular set, it is enough to show that L ′ is in F. We construct a GSM mapping which maps L to L ′ . For each x ∈ X and each a ∈ σ(G, X), let W x,a be the finite state automaton accepting {w ∈ L : σ(w, x) = a}, and let S x,a be its set of states; there are finitely many such sets. We form a (non-deterministic) generalised sequential machine M with input alphabet X and output alphabet Y as follows. The state set of M consists of the elements of the Cartesian product S x,a , together with a failure state F . For any input symbol x, any a ∈ σ(G, X), and any state s for which the x, a component is an accept state, there is an arrow in M taking s to the state of which each component is the target under x of the corresponding component of s, and such that the symbol y x,a is appended to the output. M maps L to L ′ . ✷ The next result is a (slight) generalisation of a result from [6], where it is the 'main lemma'; Bridson's result constructs a bijective asynchronous combing for a split extension of two groups out of bijective asynchronous combings for the two groups; in fact the construction also works when the extension is nearly split, and bijectivity is not strictly necessary. This seems very much to be an asynchronous result.
We need a little notation before we can state the result.
Following [22], where G is a group with normal subgroup N , we say that G is an (r, s)-split extension of N by G/N if for some H ⊆ G, N H has index at most r in G, and |N ∩ H| divides s. If G is an (r, s) extension of N for some r, s we say that G is a nearly split extension; if r = s = 1, then G is a split extension.
Suppose that groups N and H have asynchronous combings L N , L H over generating sets X, Y , and suppose that H acts as a group of automorphisms of N ; for n ∈ N , denote by n h the image of n under h. For n ∈ N , let v n = x 1 x 2 . . . x m be a word in L N which represents n. We call a word w an image Proposition 6.4 ((Nearly) split extensions) , a slight generalisation of Bridson's lemma, [6].
Let G be a nearly split extension of groups N ✁ G and H. Suppose that N and H have asynchronous F-combings L N and L H over generating sets X and Y , for some language family F which is closed under concatenation. If H ∩ N is non-trivial, suppose further that L N is an asynchronous bicombing.
Suppose also that for all n ∈ N , all y ∈ Y , and all v n and v n y in L representing n and n y respectively, v n y asynchronously fellow travels with each of the images of v n under y (Condition ( * )).
Then G has an asynchronous combing, L G . If L H and L N are bijective and the extension is split, then L G is also bijective.
Note that it is enough to require that for each n, h, some v n h asynchronously fellow travels with some image of v n under h; the rest of that condition follows from the fellow traveller properties of L N .
Proof: By proposition 5.2 (b), we lose no generality by assuming that G is equal to the product HN . In this case, we define L G = L H L N .
Throughout the proof, we use the notation v n , v ′ n for elements of the language L N which represent n, and w h , w ′ h for elements of L H representing h.
Every element of G can be written in the form hn for some n ∈ N , and some h ∈ H, so L H L N is clearly a language for G. For n 1 , n 2 ∈ N , h 1 , h 2 ∈ H, Let Γ H , Γ N , Γ G be the Cayley graphs of the three groups. Of course Γ H and Γ N embed in Γ G ; in fact each embeds many times (for any vertex of Γ G an embedding may be chosen which places the basepoint of Γ N or Γ H at that vertex). If u and u ′ are paths of Γ G which lie in the same embedding of Γ H or Γ N , then any fellow traveller condition satisfied by them in that graph clearly also holds between them in Γ G .
Suppose that n ∈ N , h ∈ H, and let x ∈ X ∪ {e}. Let u 1 = w h v n and u 2 = w ′ h v ′ nx be words in L G , for which w h and w ′ h represent h in L H , and v n and v nx represent n and nx in L N . The portions of u 1 and u 2 along w h and w ′ h asynchronously fellow travel within an embedded Γ H , and the portions from h to hg and hgx along v g and v gx asynchronously fellow travel within an embedded Γ G (based at h). Hence u 1 and u 2 asynchronously fellow travel. Now choose y ∈ Y . Since hny = hyn y , hny is represented in L G by any word u 3 = w hy v n y , for which w hy ∈ L H represents hy and v n y ∈ L N represents n y . The portions of u 1 and u 3 along w h and w hy asynchronously fellow travel in Γ G because they do in Γ H . Now the portion of u 3 from hy to hny along v n y asynchronous fellow travels with any path u ′ labelled by an image of v n y under the action of y −1 running from h to hn; edges labelled y run from any such path to the second part of u 3 . The condition ( * ) implies that any such path u ′ asynchronously fellow travels (within an embedded copy of Γ N ) with the path from h to hn labelled by v n , that is, with the second part of u 1 ; hence we have verified that u 1 and u 3 asynchronously fellow travel.
In the case where N ∩ H is trivial, any element of G has a unique representation as a product of the form hn, for h ∈ H, n ∈ N , and so the above analysis covers all representatives in L G of elements g, g ′ for which g ′ = G gx for x ∈ X ∪ {e} or g ′ = G gy for y ∈ Y . If N ∩H is a non-trivial finite group F , the proof is complete once we have verified that, for h, h ′ ∈ H and n, n ′ ∈ N , with hn = G h ′ n ′ , words of the form v h w n and v h ′ w n ′ must asynchronously fellow travel. In this case the equation hn = G h ′ n ′ implies that h ′ = hf , n ′ = f −1 n for some f ∈ F . Since F is finite, f has bounded length as a product of generators, and hence the fact that v h and v h ′ asynchronously fellow travel follows from the fellow traveller condition on H; similarly, v n and v n ′ asynchronously fellow travel, provided that L N is an asynchronous bicombing. ✷ To deduce a synchronous, rather than asynchronous, fellow traveller property, it seems that we need, in addition to synchronous fellow traveller properties in L N and L H , (a) that for all y ∈ Y , x ∈ X, x y is a generator (b) a synchronous version of ( * ). Furthernore, to get conditions for any type of bicombing seems to be more complicated. For notice that, for x ∈ X, xhg = hx h g. 'Left' fellow traveller conditions are more easily satisfied by the language L G L H , but this does not as easily have good 'right' fellow traveller properties.
Bridson observes in [6] that the condition ( * ) is satisfied by any geodesic combing of a word hyperbolic group; these combings are regular. He also shows that any finitely generated abelian group has an asynchronous combing which satisfies ( * ). For the torsion free abelian group Z n this language is found by embedding the Cayley graph in the obvious way in R n , and selecting for each element g the lexicographically earliest of the set of words which remain closest to the strange line path in R m from e to g; and in the case n = 2, this language is proved (in [7]) to be an indexed language. In both the above situations, the combings are in fact bicombings, and so the result can be applied to nearly split extensions.

Combings for nilpotent and soluble groups
In [7], Bridson's lemma was applied to show that split extensions of the form Z 2 >✁Z have asynchronous indexed (I) combings, and hence to prove that the same is true of π 1 (M ) for any compact, geometrisable 3-manifold M . Of course the construction used by Bridson has much more general application. We shall briefly observe a few consequences in this section. We see that many nilpotent, and also non-nilpotent soluble groups can be expressed as (nearly) split extensions over Z n and so have asynchronous combings. In some cases the combings are already proved (by the results of [7]) to be indexed languages. In general, it seems likely that the language for Z n described in the last paragraph of section 6 is both an indexed language and a real time language (see, for example, [23]) for all values of n; in that case the combings described in this section would also lie in these language classes. These questions are explored more fully in [13].
Where G is a non virtually abelian, nilpotent group, we cannot expect to do much better than find an indexed combing for G. For it is proved in [10] that no such group G can have a regular combing, and in [8] (and [7]) that G cannot have a bijective combing which is a bounded language. Using the latter result, it is proved in [7] that G cannot have a bijective, context-free combing (here bijectivity is essential to the proof, which deduces polynomial growth of the combing from the polynomial growth of G).
The n-th Heisenberg group which is class 2 nilpotent, is a split extension of the free abelian group c, a i b i (i = 1, . . . n) by the free abelian group a 1 , . . . a n . Hence this has a bijective, asynchronous combing.
Let U n be the group of n×n uni-uppertriangular integer matrices. This is nilpotent of both nilpotency and derived class n − 1; the terms of both the derived and lower central series are subgroups isomorphic to U n−1 , U n−2 ,. . . ,U 2 ∼ = Z.
We can express U n as a split extension of Z n−1 (found as the matrices with 1's on the diagonal, and 0's elsewhere except in the right hand column) and U n−1 (found as the matrices with 0's in the right hand column, except for the diagonal entry). Hence, by a clear induction argument U n has an asynchronous combing.
Let N = N k,2 be the free nilpotent class 2 group on k generators, with presentation x 1 , . . . x k |[[x i , x j ], x k ], ∀i, j, k Then N k,2 is a split extension of the normal abelian subgroup generated by x k and all commutators of the form [x k , x j ] by the subgroup generated by x 1 , . . . x k−1 . Hence (by induction) N k,2 has an asynchronous combing. However, for c > 2, the free nilpotent class c group N k,c on k generators x 1 , . . . , x k does not split over an abelian subgroup; hence it is not clear whether or not N k,c has a combing for c > 2.
In fact, using Bridson's lemma, the examples for N k,2 and the Heisenberg groups, and the finite variation results of proposition 5.2, many nilpotent groups can be shown to have asynchronous combings. The question is investigated further in [13]; in particular combings are found for all class 2 nilpotent groups with 2 or 3 generators or cyclic commutator subgroup.
We can use a result of Robinson ( [22]) to show that many soluble groups which are far from being nilpotent are also in this class. Robinson's result is rather general; all we really need is the version given by Segal in [24], namely that if A is a finitely generated, free abelian normal subgroup of a group G such that G/A is finitely generated and nilpotent, and such that C A (G) = 1, then G nearly splits over A; in fact a subgroup of finite index in G is a split extension of A.
Using this result we can prove the following.
Proposition 7.1 If G is polycylic, metabelian and torsion free with centre disjoint from G ′ , then G has an asynchronous combing. When G ′ has rank 2, the combing is an indexed language.
Proof: That G is polycyclic and metabelian implies that G ′ is finitely generated. By Robinson's theorem, G nearly splits over G ′ , and we can apply Bridson's lemma. ✷.
As an example, we have the group x, y, z | yz = zy, y x = z, z x = yz which is certainly not automatic (it has exponential isoperimetric inequality, see [10], theorem 8.1.3).