gr.group theory – Can one reduce to ‘reversing’ the right multiplier finite-state automata of an automatic group to obtain a biautomatic structure?

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.