Skip to main content


Pattern-matching syntax trees

I’m doing some very fun things with pattern-matching syntax trees today.

For context: I write a computer-based assessment system called Numbas, and it’s focused on assessing mathematics. A big part of that assessment involves asking the student to enter an algebraic expression as the answer to a question. How do you decide whether to mark the student’s answer as correct or not? Historically, there have been two approaches, given a representative “correct” expression written by the teacher:

  • Put the student’s answer and the correct answer into a canonical form. If their syntax trees are exactly the same, then the student’s answer is the same as the teacher’s. This is the model used by, for example, STACK.
  • Identify the variables used in the student’s answer and the teacher’s. Pick a few random numbers as values for those variables, and evaluate both expressions. If they come out to the same number, then the student’s answer is the same as the teacher’s. This is the model used by systems in the CALM line.

Read more…

Talk: Computability of Bass-Serre structures in the Grzegorczyk hierarchy

My chum the inimitable David Cushing has started a postgrad pure maths seminar at Newcastle. Because there are only a few pure postgrads here, he asked me to give a talk about the stuff I was looking at for the PhD I gave up on last year.

I’ve written a few posts here in the past about the Grzegorczyk hierarchy, computable groups, and so on, but I think this might be the first time I’ve presented my work to real people (apart from an impromptu hour-long braindump when one of the real seminar speakers cancelled and I decided to test my memory).

Read more…

Gatterdam’s proof that free products with amalgamation are En+1-computable

I haven’t posted any research in ages! I haven’t done any research in ages! Here’s a rewriting of a theorem from Ronald Gatterdam’s doctoral thesis, in more sensible language. I’ve proved the same theorem for fundamental groups of graphs of groups.

The main problem with Gatterdam’s proof was that he didn’t invent any new notation to make life simpler, so he wrote out pages and pages of very repetitive function applications.

I’ve made up a lot of notation to make dealing with functions in the Grzegorczyk hierarchy a lot easier, so you’ll probably need to refer to my draft paper for a few things. I keep all my research notes in a repository on github, by the way.

Read more…

Double coset normal form for FPAs

Liza Frenkel is visiting the department, and she wants me to write an algorithm to compute double coset representation normal forms for free products with amalgamation.

Here are some notes I typed up in write maths, see maths as she and Andrew talked. I’m just putting them up here so I don’t lose them.

F1, F2 free groups (finitely generated by X and Y, respectively)
H1F1, H2F2
an isomorphism ϕ:H1H2
i.e. we have a finite generating set (in fact a basis) {h1,,hn} for H1 (and{h1,,hn} for H2) and generating sets X,Y for F1 and F2

Consider a group generated by z1,,zm, with
G=F1H1=H2F2 has presentation X,Y|hi=hi,i=1m
Choose a set SF such that F1=sSH1sH1
(we are assuming S is infinite)
every element w of F1 is equal to w=h1sh2, for unique sS,
can do the same for F2=tTH2tH2

Let gG.
A word w representing g is in normal form if w=hi1(z)p1hi2(z)p2hik(z)pkhik+1(z), with piS, i=1k.

Suppose g=g1g2gk. Rewrite using double coset representatives

g is in reduced form if g=g1gk and
k=1 gF1 or gF2
k>1giF1H1 or giF2H2 and gi, gi+1 belong to different factors

Let ΓH1 be a folded subgroup graph of H1. Take two copies.

For some word w=h1sh2, the question is how to find s.

Read all possible loops round first graph, to get h1.
Keep reading letters round the graph until there is no edge corresponding to the current letter. Call this s1.
Start at the other end, reading loops to get h2, and then maximal s2 partway round a loop.
Then either there are no letters left to look at, and s=s1s2, or some bit f0 in the middle, and s=s1f0s2.

We want h1,h2,s to all have maximal length.


i) g=x13x22y1y2=(x12)(x1x2)(x21)1(y1)(y21)1

Membership problem

Can write the ci in normal form.
Question: Given wG in normal form, is wH3?

Constructing a folded graph which makes use of the normal form is tricky.

An E3 fgoagog and an E4 fgoagog

Over Christmas I typed up my Bass-Serre / Grzegorczyk stuff in quite a lot of detail and fairly rigorously. It’s far too much to put up here as blog posts, so here’s a link to the PDF.

The big theorem I prove says that the fundamental group of a graph of En-computable groups is En+1-computable. But are there cases when the fgoagog stays at En, and can we pin down what conditions cause it to move up to En+1? I’ve found a couple of examples which begin to answer those questions.

Corollary 1 says that if the edge groups are finitely generated then you don’t go up a level, while Corollary 2 gives an example of a graph with infinitely generated edge groups that does go up a level.

Little Facts

  1. The nth prime pnnlogn.
  2. exp(x,y):=xyE3.
  3. The Gödel encoding of a word of length n on an alphabet X is pnJ(n,n), an E3 function.

Theorem 6.7 (from the paper)

Suppose we have G=π1(G,Γ,T,v0), where Γ is finite. Suppose all the GiG are finitely generated En-computable groups, n3. Assume all the identified subgroups are En-decidable, and all the isomorphisms ϕe are En-computable. Then G is En+1-computable.

Corollary 1

Same assumptions as the Theorem 6.7, but also assume that the edge groups are finitely generated. So each edge homomorphism ϕeij sends a finitely generated subgroup EijGi to another finitely generated subgroup EjiGj. Suppose everything is En-computable.

Then G=π1(G,Γ,T,v0) is En-computable.


In the algorithm from Theorem 6.7, the potential for unbounded recursion comes from applying the edge homomorphisms repeatedly. We will show that the result of applying the edge homomorphisms repeatedly is bounded by an E3 function.

Let w be a word on G of length n. An upper bound on the number of syllables in w is n, so let’s say there are n applications of edge homomorphisms.

A homomorphism ϕeij rewrites generators xXi as words ϕeij(x)Xj. As Gi is finitely generated, there is a word ϕeij(x) of maximum, finite length kij. So a word wiEij of length m is rewritten to a word wjEj of length at most kijm.

Because the graph is finite, we can find a greatest k{kij}. So after reducing all the syllables (assuming that can be done for the input word), the resulting word in G0 has length at most knn=L.

Hence the index of the resulting word is bounded by


an E3 function, by Fact 2. So recursion on the edge homomorphisms is bounded by an En function, and so G is En-computable.

Corollary 2

We will construct a graph of E3-computable groups whose fundamental group is E4-computable.

Let G={G0,G1} be two copies of the free group on two generators, so G0=x,y and G1=a,b. The graph has a single edge e from v0 to v1, so Γ=T=({v0,v1},{e,e¯}).

Let E01={xnyxn,nN}, E10={anban,nN}. So the edge groups are infinitely generated.



Then G=π1(G,Γ,T,v0) is E4-computable.


First of all, the homomorphisms are E3-computable because words of the form anban can be recognised by an E3 function. Hence all the ingredients of the graph of groups are E3-computable.

A word of the form


will be reduced to a word on G0 whose length is proportional to fact(m)(n), where m is the number of syllables. As m depends on the input, this length can only be computed by unbounded recursion on an E3 function, so is only E4-computable.

Therefore, G is E4-computable.

Some notation for FPAs and HNN extensions

In order to define a free product with amalgamation ACB you need to define A,B,C and embeddings of C into A and B. Alternatively, instead of C you can use a homomorphism phi:AB and its inverse. A third option is to pick subgroups DA and EB and give an isomorphism between them.

All three of these options require you to define some groups and some morphisms. You can define a group nicely by giving a presentation but defining maps usually takes a few lines. So, I’d like a quicker way of describing the kinds of maps we need here.

Let’s take the third option. If we have generating sets so that D=X and E=Y, then if we can write each of the elements of X as words in Y then that defines the required isomorphism completely. After you’ve done that, the generating set Y might as well just be those words.

So how about this as a presentation for an FPA?


The bits in angle brackets are presentations of A and B. The xi are words from A and generate D, and the yi are words from B and generate E.

Because this is all on one line and delimited adequately, you can chain things together and use brackets and all that, like this contrived example:


For HNN extensions, you just need to say what the original group is, what the extending letter is, and what the identified subgroups are. So how about something like:


Apart from the different kinds of brackets being hard to distinguish visually, what have I missed?

Infinite trees are E3 (maybe)

Not completely sure about this, but here we go: I will show that an ordered, plane recursive tree is En-computable, n3, if each vertex has its number of children bounded by an En function. So this rules out trees which grow sideways a lot quicker than they grow in height, but it has to be a lot quicker.

Read more…

Lists and finite trees are E3

In order to prove the fgoagog thing we need to be able to do computations on trees at a low level of the Grzegorczyk hierarchy, so it doesn’t mess up the complexity of the whole group computation. I will give a model of finite trees that lies in E3, the same level as Cannonito/Gatterdam’s standard index for the free group. (( this post has been sitting as a draft since the beginning of May because I wanted to make some nice tree pictures, but I’d rather just publish it now. So, the trees section is copied out of my notes and might not make sense ))

Read more…

Computable categories

So I read a bit about categories after Peter Hines came up to talk to us.


A category C is a collection of objects obj(C) (or just Obj), a collection of arrows (or morphisms) hom(C) (or just Hom), and an arrow composition operation such that there is an identity arrow for each object.

An arrow has a single source object and a single target object, and is written AfB.

Read more…

The computability of a fgoagog (intro)

I’m going to write up a result I think I’ve proved, which follows on from Gatterdam’s thesis. He showed that if a group is En computable, then doing a free product with amalgamation or any number of HNN extensions to it results in a group which is at worst En+1 computable. What I’m going to say is that the fundamental group of a graph of En groups is at most En+1 computable. This isn’t unreasonable, because a fgoagog (( ‘fgoagog’ is short for ‘fundamental group of a graph of groups’, because I can’t be doing with writing that out once every three minutes )) represents a load of HNN extensions and amalgamated products.

The tactic will be to follow Gatterdam’s method for amalgamated products – if we can find an algorithm which solves the word problem of the fgoagog (decides if a word on the generators is equivalent to the identity) in En+1 time, then the whole group is En+1 computable as a quotient of the free group by the set of trivial words.

I will define an admissible form for words from the fgoagog, which is an alternating series of edge letters and words from the vertex groups, such that the edge letters make up a cycle starting and ending at the base vertex. Once we have a word in admissible form, we can reduce it by swapping the image of an edge group in one vertex with its counterpart in the vertex at the other end, and eventually a trivial word will end up as just a word on the base vertex, which is an En decision.

Clearly the process of putting a word in admissible form involves knowing something about the shape of the graph, so we need to make some En computable functions which can represent the graph and compute paths between vertices. That’s a tiny bit interesting on its own, so I’ll spend my next post talking about that. It will need some pretty pictures of trees though, which is why I’ve put off writing it for so long.