Narrow Results

We introduce a new class of groups with solvable word problem, namely groups specified by a confluent set of short-lex-reducing Knuth–Bendix rules which form a regular language. This simultaneously generalizes short-lex-automatic groups and groups with a finite confluent set of short-lex-reducing rules. We describe a computer program which looks for such a set of rules in an arbitrary finitely presented group. Our main theorem is that our computer program finds the set of rules, if it exists, given enough time and space. (This is an optimistic description of our result — for the more pessimistic details, see the body of the paper.)

The set of rules is embodied in a finite state automaton in two variables. A central feature of our program is an operation, which we call welding, used to combine existing rules with new rules as they are found. Welding can be defined on arbitrary finite state automata, and we investigate this operation in abstract, proving that it can be considered as a process which takes as input one regular language and outputs another regular language.

In our programs we need to convert several nondeterministic finite state automata to deterministic versions accepting the same language. We show how to improve somewhat on the standard subset construction, due to special features in our case. We axiomatize these special features, in the hope that these improvements can be used in other applications.

The Knuth–Bendix process normally spends most of its time in reduction, so its efficiency depends on doing reduction quickly. Standard data structures for doing this can become very large, ultimately limiting the set of presentations of groups which can be so analyzed. We are able to give a method for rapid reduction using our much smaller two variable automaton, encoding the (usually infinite) regular language of rules found so far. Time taken for reduction in a given group is a small constant times the time taken for reduction in the best schemes known (see [5]), which is not too bad since we are reducing with respect to an infinite set of rules, whereas known schemes use a finite set of rules.

We hope that the method described here might lead to the computation of automatic structures in groups for which this is currently infeasible.

Some proofs have been omitted from this paper in the interests of brevity. Full details are provided in [4].

Explicit constructions are given to illustrate the loss of control that ensues when one replaces the regular languages of automatic group theory with larger families of languages.

We define the notion of V(6) presentations that naturally generalize C(4)&T(4) and C(6) small-cancellation presentations. We consider V(6) groups (i.e. groups having V(6) presentations) where every piece is of length one. No natural geometrical interpretation is known for this class of groups. However, by using combinatorial and diagrammatical arguments, we construct a biautomatic structure for these groups.

We examine the construction of Huang and Osajda that was used in their proof of the biautomaticity of Artin groups of almost large type. We describe a slightly simpler variant of that biautomatic structure, with explicit descriptions of a few small examples, and we examine some of the properties of the structure. We explain how the construction can be programmed within the GAP system.

A general result of Epstein and Thurston implies that all link groups are automatic, but the proof provides no explicit automaton. Here we show that the groups of all torus links are groups of fractions of so-called Garside monoids, i.e., roughly speaking, monoids with a good theory of divisibility, which allows us to reprove that those groups are automatic, but, in addition, gives a completely explicit description of the involved automata, thus partially answering a question of D. F. Holt.