Can one reduce to 'reversing' the right multiplier finite-state automata of an automatic group to obtain a biautomatic structure?

Question

Let $\left( G, A, W, \left\{ R_{a} \right\}_{a \in A \cup \{ 1 \}} \right)$ be a group equipped with an automatic structure, where $G$ is the group, $A$ is a finite set of generators of $G$, $W$ is the word-acceptor finite-state automaton, and $R_{a}$ is the right multiplier finite-state automaton for $a \in A \cup \{ 1 \}$. Recall that $R_{a}$ accepts (up to padding by a symbol which I'll denote by $p$) a pair of words $(w_1, w_2)$ in $A$ if and only if $w_1$ and $w_2$ are accepted by the word-acceptor and if $w_1a = w_2$ in $G$.

I will view finite-state automata as decorated finite directed graphs (states are nodes, arrows are labelled, an arrow from $s_1$ to $s_2$ with label $l$ means that the state-transition (partial) map takes $(s_1, l)$ to $s_2$, some node is picked out as an initial state, and some set of nodes is picked out as the set of acceptor states).

It seems to me that the following simple construction equips an automatic group with a bi-automatic structure under some simplifyng assumptions.

Construction. Suppose that $1 \in A$, and that if $a \in A$ then $a^{-1} \in A$, suppose that a word $w$ is accepted by $W$ if and only if $w^{-1}$ is accepted by $W$, suppose $R_{a}$ has a single acceptor state for every $a \in A$, and suppose that the padding symbol is not used in the label of any arrow of $R_{a}$. Then we can construct $L_{a}$, the required left-multiplier finite-state automaton for a biautomatic structure for $a$, as follows.

1. Take $R_{a^{-1}}$.

2. Reverse the direction of all arrows.

3. For every occurrence of $a \in A$ in a label of an arrow, replace it by $a^{-1}$.

4. Make the single acceptance state of $R_{a^{-1}}$ the initial state of $L_{a}$.

5. Make the initial state of $R_{a^{-1}}$ the only acceptance state of $L_{a}$.

Since $aw_1 = w_2$ if and only if $w_1^{-1}a^{-1} = w_2^{-1}$, it is clear that $L_{a}$ accepts exactly the required pairs of words.

---

The following matters need to be addressed to be able to generalise the above construction. Firstly, if $R_{a}$ has more than one acceptor state, then the graph constructed as above does not quite define a finite-state automaton, since a finite-state automaton must have a single initial state. Secondly, we must handle the fact that the padding symbol might be used in some labels of of $R_{a}$. Thirdly, if $W$ accepts a word $w$, it might not accept $w^{-1}$.

I believe that these three matters can be addressed. The possibility of using the identity element of the group gives flexibility in being able to manipulate the finite-state automata of an automatic structure to obtain ones with the required properties.

But whether every automatic group is bi-automatic has been an open question for 20 or 30 years, and the answer is generally expected to be negative. Presumably there is therefore a serious problem somewhere. My question is what that problem is.

To give a hint that these three matters can be addressed, I will address a couple of them below.

Proposition 1. Suppose that the same assumptions as in the Construction above hold, except that a padding symbol may be used in some labels of $R_{a}$. Assume in addition that $W$ has the property that if $w$ is accepted by $W$, then every word obtained by adding $1$'s at the beginning or end of $w$ is also accepted by $W$. Then we can still construct a left-multiplier finite-state automaton $L_{a}$.

Proof. We can construct $L_{a}$ as follows.

1. Begin with $R_{a^{-1}}$.

2. Reverse the direction of all arrows.

3. For every occurrence of $a \in A$ in a label of an arrow, replace it by $a^{-1}$.

4. For every occurrence of the padding symbol $p$ in a label of an arrow, replace it by $1$.

5. For every path of arrows in $R_{a^{-1}}$ whose first arrow has the initial state of $R_{a^{-1}}$ as its source, and which has the property that the left (resp. right) component of the label of every arrow in the path is $1$, carry out the following steps in $L_a$.

   a) Add a disjoint copy of this path (i.e. add a new arrow for each arrow in the path, and a new state for each state in the path, with the source (resp. target) of the new arrow being the new state corresponding to the source (resp. target) of the original arrow), and carry out steps 2) and 3) for this copy.

   b) In $L_a$, glue the initial state of $R_{a^{-1}}$ to the new state corresponding to the source of the first arrow of the path in $R_{a^{-1}}$.

   c) In $L_a$, glue the source state in $R_{a^{-1}}$ (viewed as a state of $L_a$) of the last arrow of the path to the corresponding new state in the copied path in $L_a$.

   d) For every occurrence of $1$ in a label of the form $(1,-)$ (resp. $(-,1)$) in the copied path, replace it by $p$.

6. Make the single acceptance state of $R_{a^{-1}}$ the initial state of $L_{a}$.

7. Make the initial state of $R_{a^{-1}}$ the only acceptance state of $L_{a}$.

Given $(w_1, w_2)$ for which $w_1$ (resp. $w_2$) must be padded with $n$ copies of $p$ to make it the same length as $w_2$ (resp. $w_1$), then $(w_1, w_2)$ is accepted by $R_{a^{-1}}$ if and only if the pair $(w_1', w_2)$ (resp. $(w_1, w_2')$) also is accepted by $R_{a^{-1}}$, where $w_1'$ (resp. $w_2'$) is obtained by adding $n$ copies of $1$ to the beginning of it (here we appeal to our assumption that $w_1'$ (resp. $w_2'$) is accepted by $W$). In turn, $(w_1', w_2)$ (resp. $(w_1, w_2')$) is accepted by $R_{a^{-1}}$ if and only if $(w_1^{-1}, w_2^{-1})$ is accepted by $L_{a}$. Note that this argument goes through whether or not $w_1$ (resp. $w_2$) begins with a series of $1$'s; this is the reason for making a copy of the reversed path before re-labelling it in step 5) above, as opposed to simply re-labelling it.

---

Proposition 2. Suppose that the same assumptions as in the Construction above hold, except that, for any $a \in A$, a padding symbol may be used in some labels of $R_{a}$, and $R_a$ may have more than one acceptance state. Assume in addition that $W$ has the property that if $w$ is accepted by $W$, then every word obtained by adding $1$'s at the beginning or end of $w$ is also accepted by $W$. Then we can replace the automatic structure by one in which $R_a$ is replaced by a finite-state automaton $R'_a$ with a single acceptance state.

Proof. We carry out the following steps to construct $R'_a$.

1. Add a new state, which I'll denote by $T$, to $R_a$.

2. Carry out the following pair of steps for every acceptor state $S$ of $R_a$.

   a) Add an additional three states $S'$, $S'_l$, and $S'_r$ to $R'_a$. Add three arrows from $S'$ to $T$, one each labelled by $(1,1)$, $(p,1)$, and $(1,p)$. Add an arrow from $S'_l$ to $T$ labelled by $(p,1)$. Add an arrow from $S'_r$ to $T$, labelled by $(1,p)$.

   b) Duplicate every arrow in $R_a$ with target $S$ whose label does not make use of the padding symbol, and make each duplicate have target $S'$ in $R'_a$. Duplicate every arrow in $R_a$ with target $S$ whose label is of the form $\left( p, a' \right)$ (resp. $\left( a', p \right)$ for some $a' \in A$, and make each duplicate have target $S'_l$ (resp. $S'_r$) in $R'_a$.

3. Make $T$ the (only) acceptance state of $R'_a$.

We also replace the word-acceptor $W$ by one, which I'll denote by $W'$, which is the same as $W$ except that we add a new state $T$, add an arrow labelled by one from every acceptance state of $W$ to $T$, and make $T$ the (only) acceptance state of $W'$.

The effect of the replacement of $W$ by $W'$ is that every accepted word finishes with at least one $1$. We make use of this when modifying $R_a$ to $R'_a$.

---

At this point, we have reduced the general case to being able to replace an automatic structure by one in which the word-acceptor $W$ has the following properties.

1. If $w$ is accepted by $W$, then $w^{-1}$ is accepted by $W$.

2. If $w$ is accepted by $W$, then any word obtained from $w$ by adding a series of $1$'s at the beginning and/or end is also accepted by $W$.

It is easy to modify $W$ itself to a finite-state automaton with these properties, but one has to modify the right multiplier automata thereafter as well, which is more subtle, but can I believe be done.

---

Edit following Professor Holt's comments

Given Professor Holt's comments, I will explain how I think one can carry out 1. above, given that one can carry out 2. above (carrying out 2. is not very difficult). The ideas are similar to those we have already seen.

Proposition 3. Suppose that if $a \in A$, then $a^{-1} \in A$ (this is a mild assumption, typically made in the definition of an automatic group; the proof goes through if we relax to instead assuming an involution $i$ of $A$ such that $i(a)$ maps to $a^{-1}$ in $G$, but I'll assume that $a^{-1} \in A$ for notational simplicity). Suppose that $1 \in A$. Assume in addition that $W$ has the property that if $w$ is accepted by $W$, then every word obtained by adding $1$'s at the beginning or end of $w$ is also accepted by $W$. Then we can replace the automatic structure on $G$ as at the beginning of the question by one in which the word-acceptor accepts $w$ if and only if it accepts $w^{-1}$.

Proof. The easy part is to replace $W$ by a word-acceptor $W'$ defined as follows.

1. Begin with $W$.
2. Add a new state, which I'll call $T$.
3. Add an arrow, labelled by $1$, from every acceptor state of $W$ to $T$.
4. Add a new state, which I'll denote by $I$.
5. Duplicate $W$. Reverse all the arrows, and if $a \in A'$ is a label of a (reversed) duplicate arrow, replace it by $a^{-1}$.
6. Add an arrow in $W'$ labelled by $1$ from $I$ to the duplicate in the graph constructed in step 5. of each of the acceptor states of $W$. Add an arrow in $W'$ labelled by $1$ from $I$ to the initial state of $W$.
7. Choose $I$ to be the initial state of $W'$, and choose $T$ and the duplicate of the initial state of $W$ to be the (only) acceptor states of $W'$.

The effect of this is that a word $w'$ is accepted by $W'$ if and only if it can be obtained from a word $w$ accepted by $W$ by adding a single $1$ at the beginning and end of $w$, or by replacing such a word $w'$ by its inverse. In particular, $w'$ is accepted by $W'$ if and only if $(w')^{-1}$ is accepted by $W'$.

The harder part of the proof is, for $a \in A$, to replace $R_{a}$ by a new right-multiplier finite-state automaton $R'_{a}$ which accounts for the fact that $W'$ accepts more words than $W$. Nevertheless, if I am not making a mistake, it can be done, as follows. There are four parts. I'll begin with just the first two, which are quite easy, to give the idea, and then I'll describe the last two at the end.

1. Begin with $R_{a}$.
2. Add a new state, which I'll call $T_1$.
3. Do the same as in step 2. of the proof of Proposition 2 for the acceptor states of $R_a$ and $T_1$.
4. Add a new state, which I'll denote by $I$.
5. Duplicate $R_{a^{-1}}$. Carry out steps 2. - 5. of the proof of Proposition 1 for this duplicate. Add a new state $T_2$ to the resulting graph, and do the same as in step 2. of the proof of Proposition 2 for $T_2$ and the duplicate of the initial state of $R_{a^{-1}}$. Finally, swap the left and right parts of every label of the resulting graph.
6. Add an arrow in $R'_a$ labelled by $(1,1)$ from $I$ to the duplicate in the the graph constructed in step 5. of each of the acceptor states of $R_{a^{-1}}$. Add an arrow in $R'_a$ labelled by $(1,1)$ from $I$ to the initial state of $R_a$.
7. Choose $I$ to be the initial state of $R'_a$, and choose $T_1$ and $T_2$ to be the (only, so far) acceptor states of $R'_a$.

The effect of the construction so far is as follows.

1. If $w_1$ and $w_2$ are accepted by $W$ and $w_1a = w_2$, then $(w_1, w_2)$ is accepted by $R'_a$ after adding a $1$ at the beginning and end of both $w_1$ and $w_2$.
2. If $w_1$ and $w_2$ are accepted by $W$ and $(w_1)^{-1}a = (w_2)^{-1}$, then $\left(w_1^{-1}, w_2^{-1} \right)$ is accepted by $R'_a$ after adding a $1$ at the beginning and end of both $w_1$ and $w_2$.

Here 1. comes from the presence of $R_a$ as a 'prong' of $R'_a$, whereas 2. comes from the presence of a duplicated and reversed (and further modified) $R_{a^{-1}}$, with labels swapped, as a prong of $R'_a$, since $w_1^{-1}a = w_2^{-1}$ if and only if $w_2^{-1}a^{-1} = w_1^{-1}$.

It remains to further modify $R'_a$ to handle the following two cases.

3. If $w_1$ and $w_2$ are accepted by $W$ and $w_1^{-1}a = w_2$, then $\left( w_1^{-1}, w_2 \right)$ should be accepted by $R'_a$ after adding a $1$ at the beginning and end of both $w_1$ and $w_2$.
4. If $w_1$ and $w_2$ are accepted by $W$ and $w_1a = w_2^{-1}$, then $\left(w_1, w_2^{-1} \right)$ is accepted by $R'_a$ after adding a $1$ at the beginning and end of both $w_1$ and $w_2$.

I will describe how to handle 3.; the case of 4. is entirely analogous.

8. Begin with the construction of $R'_a$ as we left it after step 7. above.
9. Consider the subgraph of $R_a$ consisting of all edges (and their vertices) whose left label maps to $1$ in $G$.
10. For every vertex $S$ in the graph of 9., duplicate the subgraph of that graph consisting of all edges (and their vertices) which belong to some path from the initial state of $R_a$ to $S$. Reverse all arrows in this duplicate, and if $(e,a)$ is a label of an arrow of the duplicate, label the reverse of that arrow by $a^{-1}$. Add a new state $T_3$ to this reversed duplicate, and add an arrow from $S$ to $T_3$ labelled by $1$.
11. Duplicate in addition the subgraph of the graph in 9. consisting of all edges (and their vertices) which belong to some path from $S$ to an acceptor state of $R_a$. If an arrow has label $(e, a)$, label it instead by $a$ in the duplicate. Add a new state $T_4$ to this subgraph, and do the same as in step 2. of the proof of Proposition 2 for the acceptor states of this subgraph and $T_3$.
12. Take the tensor (i.e. category-theoretic) product of the graphs of 10. and 11., with that of 10. being the left component.
13. Let $V$ be a vertex of the graph of 12. whose right component is $T_4$, but whose left component is not $T_3$. Let us denote this left component by $V_l$. Duplicate the subgraph of the graph of 10. which consists of all edges which occur on some path from $V_l$ to $T_3$, and glue the vertex $V_l$ in this duplicate to the vertex $V$. If $a^{-1}$ is the label of an arrow of the duplicate, replace it by $\left( a^{-1}, p \right)$, recalling that $p$ is the padding symbol.
14. Let $V$ be a vertex of the graph of 12. whose left component is $T_3$, but whose right component is not $T_4$. Let us denote this right component by $V_r$. Duplicate the subgraph of the graph of 11. which consists of all edges which occur on some path from $V_r$ to $T_4$, and glue the vertex $V_r$ in this duplicate to the vertex $V$. If $a$ is the label of an arrow of the duplicate, replace it by $\left( p, a \right)$.
15. For every vertex $S$ of the graph of 9, every graph constructed as in 10. - 14. with respect to $S$ has a vertex whose left component is the initial state of $R_a$, and whose right component is $S$. Glue all of these vertices together.
16. Add an arrow labelled by $(1,1)$ from $I$ (i.e. the vertex added in step 4.) to the glued state of 15.
17. Make all vertices which have either $T_3$ as the left component or $T_4$ as the right component (or have both of these) acceptor states of $R'_a$.

What we have done here is add a third 'prong' to $R'_a$ which, up to adding a $1$ at the beginning and end of words where appropriate, accepts a pair $\left( w_1^{-1}, w_2 \right)$ if and only if $\left(1, w_1w_2\right)$ is accepted by $R_a$, i.e. if and only if $a = w_1w_2$, which is the case if and only if $w_1^{-1}a = w_2$, as required.

It remains only to add a fourth prong to $R'_a$ in the same way as in 8. - 17., but swapping the left and right components of the label pairs throughout the construction, i.e. working with labels of the form $(a,e)$ rather than $(e,a)$ in 9., where $e$ maps to $1$ in $G$, etc.

Answer 1

I would like to give a couple of examples, which I hope illustrate my belief that you cannot derive a biautomatic structure for a group from an arbitrary automatic structure by some kind of general formal construction that involves altering the word acceptor $W$ so that $w \in L(W) \Rightarrow w^{-1} \in L(W)$.

Consider first the free abelian group on two generators $a$ and $b$. This has an automatic structure with $L(W) = \{a^mb^n : m,n \in {\mathbb Z}\}$. (This is a so-called shortlex structure.)

This is in some ways a bad example, because it is already a biautomatic structure, so we don't need to do anything, but if we try and adjust it so that $L(W)$ is closed under inversion, then the new $W$ would have to accept $\{b^ma^n : m,n \in {\mathbb Z}\}$ as well as all of the original language.

But now the equality recognizing automaton has to accept the words $\{ (a^nb^n,b^na^n) : n \in {\mathbb Z} \}$, which it cannot do, because these word-pairs do not fellow-travel.

For an example that is not already a biautomatic structure, consider the group ${\mathbb Z} \wr C_2$ with presentation $\langle a,b,t \mid ab=ba, t^2=1, a^t=b \rangle$.

That has the shortlex automatic structure with $$L(W) = \{a^mb^n : m,n \in {\mathbb Z}\} \cup \{a^mb^nt : m,n \in {\mathbb Z}\}.$$

Now this is not a biautomatic structure, and I don't believe that there is any easy way of deriving a biautomatic structure from it that just involves manipulation of automata. To get a biautomatic structure, you (apparently) have to use a language containing words $(ab)^ma^n$, $(ab)^ma^n$, $(ab)^ma^nt$, $(ab)^ma^nt$, which is not related in any obvious way to the original.

Other examples are even less transparent. For Artin groups of large type (i.e. all edge labels at least 3), we have shortlex automatic structures on the natural generators, but again these are not in general biautomatic structures. It has now been proved that these groups are biautomatic, but that uses the theory of systolic groups (a geometric condition involving action on systolic complexes), which results in structures that are very far removed from the original.