Group theory with grep?

Question

While reading Bill Thurston's obituary in the Notices of the AMS I came across the following fascinating anecdote (pg. 32):

Bill’s enthusiasm during the early stages of mathematical discovery was infectious. Once, while sitting in his living room, Bill said to me, “I can do this group with grep,” which was sort of strange to hear at first. But being his student I knew just enough computerese to have an inkling of what he was saying: he was able to compute in that group with the UNIX utility for processing regular expressions using finite deterministic automata. From there, it was exciting to observe the quick unfolding of the theory of automatic groups.

Looking through David Epstein's Word Processing in Groups I can see that there are indeed connections between automatic groups and regular expressions that should allow faster algorithms for certain computations e.g. solving the word problem.

But is there a concrete example of a group-theoretic computation with grep?

Answer 1

I wrote that quote, and I'll take the hint of @SamNead and try to write an answer, although the best I can do is to write a somewhat speculative extension of the story behind the quote, laced with some mathematical musings.

From my memories of that period (sometime in the mid-late 1980's), I only vaguely recall looking at any actual output of Bill Thurston's computer experiments using grep to compute in groups. My memory is not at all precise enough regarding any actual examples he might have produced, but I suspect that they must have been pretty simple examples, for the following reasons.

In the theory of regular languages and FDAs (finite deterministic automata), there are reasonably simple algorithms for going back and forth between regular expressions and finite deterministic automata, producing an expression matching exactly the words accepted by a given automaton, and producing an automaton accepting exactly the words matched by a given expression. The algorithm from regular expressions to FDAs works pretty efficiently and is the basis of the grep utility. The algorithm from FDAs to regular expressions seems to be horribly inefficient, as reported by Derek Holt in his comment. So one might expect that writing an actual regular expression that matches normal forms for a certain group could be quite tedious.

Nonetheless if one is clever enough one can sometimes just manually come up with a regular expression to match a given language. See the exercise Derek Holt suggests in his comment; carrying out that exercise will likely give you the most direct answer to your question.

I suspect that this is what Thurston was doing during this discovery period: noticing that certain finitely generated groups have a regular language of normal forms.

Thurston was also very familiar with concepts of cone types (developed by Jim Cannon around that time; Thurston and Cannon talked together a lot during that period). So at some point during this process he certainly also noticed the connections between cone types and what we now call the 2-tape "multiplier automata" which are at the heart of the theory of automatic groups. It is tempting to speculate whether Thurston's grep experiments extended to writing regular expressions for 2-tape multiplier automata, but honestly I have no idea.

Answer 2

As Derek Holt suggested in a comment, it seems Thurston was indeed thinking of word acceptors that returned normal forms for elements of automatic groups. From a 1989 research report of his titled Groups, tilings and finite state automata: (pg. 41)

A good example is the Unix utility egrep. The word acceptor for Z, for instance, could be specified by the regular expression a*|A* where the symbol * denotes zero or more repetitions of the preceding object, and the symbol | means ‘or’. The command egrep '^a*|A*$' prints out all lines of its inputs which are accepted by WA $\dots$

He goes on in page 42:

For instance, a word acceptor which accepts only words in reduced form for the free group $\langle ab|\rangle$ is illustrated in 11.3. The corresponding egrep command is egrep '^(b+|B+)?((a+|A+)(b+|B+))*(a+|A+)?$' $\dots$

With a text file as input one can easily check that these commands are the correct word acceptors.