Combing nilpotent and polycyclic groups
               =======================================

(with Derek Holt and Sarah Rees).


The notable exclusions from the family of automatic groups are those
nilpotent groups which are not virtually abelian, and the fundamental
groups of compact 3-manifolds based on the Nil or Sol geometries.
Of these, the 3-manifold groups have been shown by Bridson and Gilman
to lie in a family of groups defined by conditions slightly more general
than those of automatic groups, that is, to have combings which lie in
the formal language class of indexed languages.  In fact, the combings
constructed by Bridson and Gilman for these groups can also be seen to be
real-time languages (that is, recognised by real-time Turing machines).
This article investigates the situation for nilpotent and polycyclic
groups.  It is shown that a finitely generated class 2 nilpotent group
with cyclic commutator subgroup is real-time combable, as are also all 2
or 3-generated class 2 nilpotent groups, and groups in specific families
of nilpotent groups (the finitely generated Heisenberg groups, groups of
unipotent matrices over Z and the free class 2 nilpotent groups).
Further it is shown that any polycyclic-by-finite group embeds in a
real-time combable group.  All the combings constructed in the article
are boundedly asynchronous, and those for nilpotent-by-finite groups have
polynomially bounded length functions.