# 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.

# 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).

# Gatterdam’s proof that free products with amalgamation are ${\mathcal{E}}^{n+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.

# 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.

Suppose:
${F}_{1}$, ${F}_{2}$ free groups (finitely generated by $X$ and $Y$, respectively)
${H}_{1}\le {F}_{1}$, ${H}_{2}\le {F}_{2}$
$\mathrm{\exists }$ an isomorphism $\varphi :{H}_{1}\to {H}_{2}$
i.e. we have a finite generating set (in fact a basis) $\left\{{h}_{1},\dots ,{h}_{n}\right\}$ for ${H}_{1}$ (and$\left\{{h}_{1}\prime ,\dots ,{h}_{n}^{\prime }\right\}$ for ${H}_{2}$) and generating sets $X,Y$ for ${F}_{1}$ and ${F}_{2}$

Consider a group generated by ${z}_{1},\dots ,{z}_{m}$, with
${z}_{1}={h}_{1}\left({x}_{1},\dots ,{x}_{n}\right)={h}_{1}\prime \left({y}_{1},\dots ,{y}_{r}\right),\dots ,{z}_{m}={h}_{m}\left({x}_{1},\dots ,{x}_{n}\right)={h}_{m}^{\prime }\left({y}_{1},\dots ,{y}_{r}\right)$
$G={F}_{1}\underset{{H}_{1}={H}_{2}}{\ast }{F}_{2}$ has presentation $⟨X,Y|{h}_{i}={h}_{i}^{\prime },i=1\dots m⟩$
Choose a set $S\subseteq F$ such that ${F}_{1}=\bigcup _{s\in S}{H}_{1}s{H}_{1}$
(we are assuming $S$ is infinite)
every element $w$ of ${F}_{1}$ is equal to $w={h}_{1}s{h}_{2}$, for unique $s\in S$,
${h}_{1},{h}_{2}\in {H}_{1}$
can do the same for ${F}_{2}=\bigcup _{t\in T}{H}_{2}t{H}_{2}$

Let $g\in G$.
A word $w$ representing $g$ is in normal form if $w={h}_{{i}_{1}}\left(z\right){p}_{1}{h}_{{i}_{2}}\left(z\right){p}_{2}\dots {h}_{{i}_{k}}\left(z\right){p}_{k}{h}_{{i}_{k+1}}\left(z\right)$, with ${p}_{i}\in S$, $i=1\dots k$.

Suppose $g={g}_{1}{g}_{2}\dots {g}_{k}$. Rewrite using double coset representatives
$g={h}_{1}\left(X\right){s}_{1}{h}_{2}\left(Y\right){t}_{2}{h}_{3}\left(X\right)\dots$

$g$ is in reduced form if $g={g}_{1}\dots {g}_{k}$ and
$k=1⇒$ $g\in {F}_{1}$ or $g\in {F}_{2}$
$k>1⇒{g}_{i}\in {F}_{1}\mathrm{\setminus }{H}_{1}$ or ${g}_{i}\in {F}_{2}\mathrm{\setminus }{H}_{2}$ and ${g}_{i}$, ${g}_{i+1}$ belong to different factors

Let ${\mathrm{\Gamma }}_{{H}_{1}}$ be a folded subgroup graph of ${H}_{1}$. Take two copies.

For some word $w={h}_{1}s{h}_{2}$, the question is how to find $s$.

Algorithm:
Read all possible loops round first graph, to get ${h}_{1}$.
Keep reading letters round the graph until there is no edge corresponding to the current letter. Call this ${s}_{1}$.
Start at the other end, reading loops to get ${h}_{2}$, and then maximal ${s}_{2}$ partway round a loop.
Then either there are no letters left to look at, and $s={s}_{1}{s}_{2}$, or some bit ${f}_{0}$ in the middle, and $s={s}_{1}{f}_{0}{s}_{2}$.

We want ${h}_{1},{h}_{2},s$ to all have maximal length.

Example

i) $\begin{array}{rl}g& ={x}_{1}^{3}{x}_{2}^{2}{y}_{1}{y}_{2}\\ & =\left({x}_{1}^{2}\right)\left({x}_{1}{x}_{2}\right)\left({x}_{2}^{-1}{\right)}^{-1}\cdot \left({y}_{1}\right)\left({y}_{2}^{-1}{\right)}^{-1}\end{array}$

## Membership problem

$\begin{array}{rl}G& ={F}_{1}\underset{{H}_{1}={H}_{2}}{\ast }{F}_{2}\\ {H}_{3}& =⟨{c}_{1},\dots ,{c}_{l}⟩⩽G\end{array}$
Can write the ${c}_{i}$ in normal form.
Question: Given $w\in G$ in normal form, is $w\in {H}_{3}$?

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

# An ${E}_{3}$ fgoagog and an ${E}_{4}$ 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 ${E}_{n}$-computable groups is ${E}_{n+1}$-computable. But are there cases when the fgoagog stays at ${E}_{n}$, and can we pin down what conditions cause it to move up to ${E}_{n+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 $n$th prime ${p}_{n}\approx n\mathrm{log}n$.
2. $\mathrm{exp}\left(x,y\right):={x}^{y}\in {E}_{3}$.
3. The Gödel encoding of a word of length $n$ on an alphabet $X$ is $\le {p}_{n}^{J\left(n,n\right)}$, an ${E}_{3}$ function.

### Theorem 6.7 (from the paper)

Suppose we have $G={\pi }_{1}\left(\mathbf{G},\mathrm{\Gamma },T,{v}_{0}\right)$, where $\mathrm{\Gamma }$ is finite. Suppose all the ${G}_{i}\in \mathbf{G}$ are finitely generated ${E}_{n}$-computable groups, $n\ge 3$. Assume all the identified subgroups are ${E}_{n}$-decidable, and all the isomorphisms ${\varphi }_{e}$ are ${E}_{n}$-computable. Then $G$ is ${E}_{n+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 ${\varphi }_{{e}_{ij}}$ sends a finitely generated subgroup ${E}_{ij}\le {G}_{i}$ to another finitely generated subgroup ${E}_{ji}\le {G}_{j}$. Suppose everything is ${E}_{n}$-computable.

Then $G={\pi }_{1}\left(\mathbf{G},\mathrm{\Gamma },T,{v}_{0}\right)$ is ${E}_{n}$-computable.

### Proof

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 ${E}_{3}$ 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 ${\varphi }_{{e}_{ij}}$ rewrites generators $x\in {X}_{i}$ as words ${\varphi }_{{e}_{ij}}\left(x\right)\in {X}_{j}^{\ast }$. As $G-i$ is finitely generated, there is a word ${\varphi }_{{e}_{ij}}\left(x\right)$ of maximum, finite length ${k}_{ij}$. So a word ${w}_{i}\in {E}_{ij}$ of length $m$ is rewritten to a word ${w}_{j}\in {E}_{j}$ of length at most ${k}_{ij}m$.

Because the graph is finite, we can find a greatest $k\in \left\{{k}_{ij}\right\}$. So after reducing all the syllables (assuming that can be done for the input word), the resulting word in ${G}_{0}$ has length at most ${k}^{n}n=L$.

Hence the index of the resulting word is bounded by

${p}_{{k}^{n}n}^{J\left({k}^{n}n,{k}^{n}n\right)},$

an ${E}_{3}$ function, by Fact 2. So recursion on the edge homomorphisms is bounded by an ${E}_{n}$ function, and so $G$ is ${E}_{n}$-computable.

$◻$

### Corollary 2

We will construct a graph of ${E}_{3}$-computable groups whose fundamental group is ${E}_{4}$-computable.

Let $\mathbf{G}=\left\{{G}_{0},{G}_{1}\right\}$ be two copies of the free group on two generators, so ${G}_{0}=⟨x,y⟩$ and ${G}_{1}=⟨a,b⟩$. The graph has a single edge $e$ from ${v}_{0}$ to ${v}_{1}$, so $\mathrm{\Gamma }=T=\left(\left\{{v}_{0},{v}_{1}\right\},\left\{e,\overline{e}\right\}\right)$.

Let ${E}_{01}=⟨\left\{{x}^{-n}y{x}^{n},n\in \mathbb{N}\right\}⟩$, ${E}_{10}=⟨\left\{{a}^{-n}b{a}^{n},n\in \mathbb{N}\right\}⟩$. So the edge groups are infinitely generated.

Define

$\begin{array}{rl}{\varphi }_{e}\left({x}^{-2n}y{x}^{2n}\right)& ={a}^{\left(-2n\right)!}b{a}^{\left(2n\right)!},\\ \\ {\varphi }_{\overline{e}}\left({a}^{-2n-1}b{a}^{2n+1}\right)& ={x}^{-\left(2n\right)!-1}y{x}^{\left(2n\right)!+1}.\end{array}$

Then $G={\pi }_{1}\left(\mathbf{G},\mathrm{\Gamma },T,{v}_{0}\right)$ is ${E}_{4}$-computable.

### Proof

First of all, the homomorphisms are ${E}_{3}$-computable because words of the form ${a}^{-n}b{a}^{n}$ can be recognised by an ${E}_{3}$ function. Hence all the ingredients of the graph of groups are ${E}_{3}$-computable.

A word of the form

$e{a}^{-1}{e}^{-1}\dots {x}^{-1}e{a}^{-1}{e}^{-1}{x}^{-n}y{x}^{n}ea{e}^{-1}x\dots ea{e}^{-1}$

will be reduced to a word on ${G}_{0}$ whose length is proportional to ${\mathrm{fact}}^{\left(m\right)}\left(n\right)$, where $m$ is the number of syllables. As $m$ depends on the input, this length can only be computed by unbounded recursion on an ${E}_{3}$ function, so is only ${E}_{4}$-computable.

Therefore, $G$ is ${E}_{4}$-computable. $◻$

# Some notation for FPAs and HNN extensions

In order to define a free product with amalgamation $A{\ast }_{C}B$ 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:A\to B$ and its inverse. A third option is to pick subgroups $D\subset A$ and $E\subset B$ 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}^{\ast }$ then that defines the required isomorphism completely. After you’ve done that, the generating set $Y$ might as well just be those words.

$⟨{a}_{1},{a}_{2},\dots |{R}_{A}⟩\left[{x}_{1}={y}_{1},{x}_{2}={y}_{2},\dots \right]⟨{b}_{1},{b}_{2},\dots |{R}_{B}⟩$

The bits in angle brackets are presentations of $A$ and $B$. The ${x}_{i}$ are words from $A$ and generate $D$, and the ${y}_{i}$ 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:

$\left(⟨a,b⟩\left[b=c\right]⟨c,d|cd=dc⟩\right)\left[a=e\right]⟨e,f⟩$

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:

$⟨{g}_{1},{g}_{2},\dots |{R}_{G}⟩\left[t|{x}_{1}={y}_{1},{x}_{2}={y}_{2},\dots \right]$

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

# Infinite trees are ${E}_{3}$ (maybe)

Not completely sure about this, but here we go: I will show that an ordered, plane recursive tree is ${E}_{n}$-computable, $n\ge 3$, if each vertex has its number of children bounded by an ${E}_{n}$ 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.

# Lists and finite trees are ${E}_{3}$

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 ${E}_{3}$, 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 ))

# Computable categories

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

## Categories

A category $C$ is a collection of objects $obj\left(C\right)$ (or just Obj), a collection of arrows (or morphisms) $hom\left(C\right)$ (or just Hom), and an arrow composition operation $\circ$ 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 $A\stackrel{f}{\to }B$.

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 ${E}_{n}$ computable, then doing a free product with amalgamation or any number of HNN extensions to it results in a group which is at worst ${E}_{n+1}$ computable. What I’m going to say is that the fundamental group of a graph of ${E}_{n}$ groups is at most ${E}_{n+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 ${E}_{n+1}$ time, then the whole group is ${E}_{n+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 ${E}_{n}$ 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 ${E}_{n}$ 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.