[ Main page  Part I. Geometry and combinatorics  Part III. Multiplication  Part IV. Closures ] 
In working with Coxeter groups on a computer,
the most basic questions to be answered are

In any Cartan realization, the elements of
Why are roundoff problems potentially serious?
For finite and affine groups they probably aren't,
but for groups where the Tits cone is acute it may well be  as
a chamber 
A method that is subject to some of the criticisms
in the previous section, but is nonethless
sometimes convenient, is one which represents each
element of
This is especially efficient because the number
One nice feature of this representation of
elements is that we can use it to
find the reduced expressions to use in multiplication. We know that
Exercise 1.
(Research problem) Suppose the realization to be the standard one.
Take 
The first interesting combinatorial result was found by Jacques Tits.
In principle, in showing that one word in
Changing Tit's terminology slightly, I define
reduction of a word in
Theorem 1. (Jacques Tits) In order for two words
Proof. If the intersection
is nonempty,
then certainly the two
are equivalent.
The nontrivial half of the Theorem
is to show that if
In particular, as the illustration shows,
there is a natural order in which to count such points,
and the proof proceeds by induction on
the index of the pair
Suppose now that
Suppose that there exists
Since
Suppose that So now we may assume that
So now we may assume (a)
Because of the potentially huge size of Exercise 2. (A minor research problem) Turn this proof into an algorithm that starts with a chain of relations allowing either insertions or deletions and winds up with a pair of reductions. 
We are going to be interested in recognizing patterns in
reduced expressions for elements of
Let's look again at the dihedral group of order
This can also be described by a diagram:
in which paths starting at the dotted disc parametrize ShortLex words in the group, matching labeled edges between nodes and generators in a word. No surprises here; there are exactly as many nodes in the diagram as there are elements in the group. Something slightly more curious is that paths in this smaller diagram also parametrize the same words:
But the real point to be made occurs with the infinite group
but also by paths in this one:
Of course, this is a wonderul compression! It is the first example we have seen of a phenomenon that we shall see much of later on, and one that seems to be ubiquitous in this subject: infinite Coxeter groups are often represented well by finite structures. Diagrams of the sort we are looking at  roughly speaking, directed labeled graphs together with a designated starting point  are called automata or state machines in the theory of languages. They play an important role in how computers parse input, among other things. The sets of strings that are recognized by such diagrams are called regular expressions. They are called automata because paths tracing through one follow a program with a strictly limited number of options  if they have arrived at a node, then what they can do subsequently depends only on that node, not on the history of how they got to it. The paths have limited memory, like a simple mechanical toy. Exercise 3.
If 
I believe, for reasons that will be laid out
later on, that regular expressions will prove to be unavoidable
in understanding important phenomena associated to Coxeter groups.
How important remains to be seen. Nonetheless, for this reason
it seems useful to look at them in more detail. There are many
points that haven't been touched upon yet, and a few that haven't
been made very precise.
I should also point out that by no means all interesting languages are regular. The simplest example is that of balanced left and right parenthetical expressions. The point is that a regular language has only a limited memory, whereas whether or not a parenthesis `)' is balanced somewhere in an expression by a `(' may involve searching back to the beginning of the expression. Deterministic automataThe following are examples of how one normally writes positive rational numbers:
These are not:
Note that we are not restricting ourselves to reduced fractions.
We can put together
a recipe for expressing a positive rational number:
(1) To write a positive integer we
write a sequence of nonnegative digits, starting
with a positive one.
(2) To write a positive rational number,
write a positive integer,
followed optionally by a slash
This looks like a finite automaton, but there is a
new feature  the red nodes. The point is
that not all paths in this diagram lead to
an acceptable expression for a fraction. The prefix of a valid expression
for a fraction may not be itself valid.
For example, the empty string is not acceptable.
Also, a single
So we have a precise definition:
a deterministic automaton is a directed graph together with
an alphabet (also called the set of imput symbols).
The edges in the graph are labeled by symbols
from the alphabet, and there is at most
one edge with a given label leaving any node.
Some of the nodes are designated as accepting states
and one of them as the start state. To such a graph
is associated a language in the alphabet Exercise 4. Design a finite automaton that represents real numbers. Why can't we expect a finite automaton to recognize reduced fractions? Whether an expression is recognized by a finite automaton depends on its form, not its content  its syntax, not its semantics. Deciding whether a fraction is reduced or not involves thinking about the meaning of fractions, not just their form. We shouldn't expect anything as simple as a finite automaton to handle this sort of thing. Syntactical analysis is often, however, a preliminary to semantic interpretation. Nondeterministic automataThere are also nondeterministic automata. Or, more properly, notnecessarilydeterministic automata. I abbreviate the term as NDA. There are three modifications: (1) There may be several starting states; (2) there may be unlabeled edges; (3) there may be several edges with a given label leaving a node. IfProposition 2. Every finite NDA is equivalent to a finite deterministic one.
Proof.
Suppose given an automaton
The nodes of the new automaton are the saturated subsets of
the nodes of
The new automaton may be huge. In practice, most of the
new nodes may be thrown away, because they are not
attainable from the start state. As an extreme example, if
The potential exponential growth does occasionally happen. Construction of the deterministic automatonIrredundant automataA node in an automaton is called redundant if no path from a start state reaches it. Eliminating these produces an equivalent automaton.Dead statesAn automaton is called complete if for each nodeInversionThe usefulness of nondeterministic automata becomes clear when one tries to build an automaton recognizing the same strings as an automatonProposition 3. The inverted words of a regular language also form a regular language. This accounts for the result that InverseShortLex is a regular language if ShortLex is. ConcatenationIfProposition 4. The concatenation of two regular languages is again regular.
Proof. Let
The problem is that there is no way to see how the automata for
Make up a new version of RepetitionIfProposition 5. The repetition of a regular language is again regular.
Proof. Suppose AlternationIfProposition 6. The alternation of two regular languages is again regular.
Proof. Suppose NegationIfProposition 7. The negation of a regular language is regular.
Proof.
Suppose that IntersectionIfProposition 8. The intersection of two regular languages is again regular. Proof. It is the negation of the alternation of their negations. Minimal automataAny language is recognized by a unique smallest automaton. There is an efficient algorithm to compute the equivalent minimal automaton from any given finite one.
Here's an example we have seen already. The tautologous automaton recognizing
reduced words for
But now some of the nodes are equivalent in the sense that
the paths out of these nodes are the same  i.e. the options for continuing
a word from that node are the same. In this picture, all the nodes
coloured green are equivalent since all paths out of any of them
is just a repeated
We can collapse all of the same colour to a single point, to get a new equivalent automaton:
This construction is always valid, but a bit of care is
required. It is not the full set of words leaving a node
which is important, but just those which lead to acceptable
nodes. For example, a few extra edges could always be added to
a dead state without changing things substantially.
If The minimization algorithmThere is an algorithm for producing the minimal automaton equivalent to a given one which is remarkably efficient. To explain it, I begin by putting the problem more constructively. Let
Suppose we have already found the blocks
In fact there exists an algorithm with time dependence
This algorithm solves a slightly more general problem,
one which occurs when dealing with Coxeter groups.
Suppose we are given a collection of maps

Let's look at the
ShortLex
words for a more complicated infinite Coxeter group,
that with Coxeter diagram .
It is an affine group, and we shall look at it as generated by affine reflections.
There are three generators, which I write as 1, 2,
3. Each element of the group is represented by a
ShortLex word, hence a path of coloured arrows
from the chamber
Certain things are not difficult to see in this image.
Every nonempty ShortLex expression starts with
one of the three symbols 1, 2, or
3, so the chambers other than
It is significant that each of these regions is convex. Indeed, it appears that all of the regions comprised of a single chamber together with its successors in the tree are convex. We shall why this is so in a moment.
The question is whether we can recognize in this tree a repetition of
patterns similar to that in the tree for
There are lots of such cycles  in the following picture, each yellow chamber represents the same position in such a cycle:
But there are more interesting repetitions:
Start out at
Two chambers will be called ShortLex congruent
if the pattern of transitions in the ShortLex tree
out of each of them is the same. If this happens,
then there exists an element of the Weyl group
transforming one of these patterns onto the other.
It turns out for
Note that there are indeed loops
This is not an isolated case. It is a very beautiful result of Brigitte Brink and Bob Howlett that: Theorem 9. For any Coxeter group, there are finite automata recognizing ShortLex expressions, InverseShortLex expressions, and reduced words in the group. We shall look at the proof in subsequent sections. That InverseShortLex is a regular language follows formally from the regularity of ShortLex, since it is just the reversed language. It is reasonable to think of both of these as lacking in significance, perhaps to be considered results in applied rather than pure mathematics. But that reduced words should also be recognized by a finite automaton must be a fundamental property of Coxeter groups. For finite and affine groups it is not a very deep result; it is equivalent to other more familiar properties of these groups. But for other groups it is not at all a trivial fact, and that it has taken so long to be discovered is likely just a sign that not much work has been devoted to these groups.
Here is the finite automaton recognizing reduced words for
Its symmetry arises from the symmetry of the Coxeter diagram.
Embedded in it are three hexagons, which are the finite automata
for the dihedral
groups of two generators, each of order Exercise 5. Prove this last assertion  that any finite automaton recognizing the reduced expressions for a finite Coxeter group have to have size at least that of the group itself. 
For each
Then One advantage of knowing the automaton for ShortLex is that generation of elements is then easy. 
Proposition 11. The reduced words for those elements of
Proof. The reduced words are a regular language,
and those which uniquely represent an element are,
by Tits' Theorem, those which do not contain
either side of a braid relation. But those words
in


