Let *P* be a permutation group with some generating set *S* and let *W* be the word acceptor automaton of *P*, if I know the value of *k* (*k-fellow-traveller property* of CayleyGraph CG(P,S)). 
I realized that the number of states *W* changes in function of *k*, when value of *k* is "low", the total of states of *W* is also low. 


For instance, if we have the following permutation groups (defined by the parameter *p*):


*P1*, where *S={(i,i+1) in Symm\_\_p, 1<=i< p}* i.e. elements i-th and (i+1)-th of a permutation are interchanged. The CG(P1,S) is called blubble-sort graph


*P2*, where *S={(1,i) in Symm\_\_p, 1 < i < = p }* i.e. the first and i-th elements of a permutation are interchanged. The CG(P2, S) is called star graph


*P1* and *P2* have order p!, I have made test with the library kbmag for 6 values of p=[4,9] and I found:


1)for P1 and when p=4,5,6,7,8,9, it is possible that k is bounded by 4
2)for P2, the value of k increases with respect to p
3)in all cases the *W* of P2 has much more states than the *W* of *P1*


My questions is if there is a relationship between the size of *W* and the value of *k*?
I have realized that depends of the lexicographical order over the generating set S, I can improve the value of k (get a low value) and also the size of *W*. Another question is how choose the best lexicographical order?



k-fellow traveler property and automatic structur
The first point to note is that it is not so much the value of $k$ in the $k$-fellow-traveller property that determines the number of states of $W$, but rather the number $d$, say, of *word-differences*. These are the labels of the shortest words in the Cayley-graph that connect corresponding vertices in fellow-travelling paths. So $k$ is just the maximum length of a word-difference. You could have small $k$ but a large number ($O(|X|^{k+1})$) word-differences or in some examples $k$ could be large but with relatively few word-differences. The number of states of $W$ depends heavily on $d$. In fact $W$ can be computed from the set of word-differences using standard operations on automata. Since this involves determinizing a non-deterministic automaton, the number of states could potentially grow exponentially with $d$, but fortunately that does not tend to happen in typical examples (presumably because the word acceptor is in in some sense a natural object to be constructing).


Typically, automatic structures do not provide an efficient method of computing with finite groups. For arbitrary finite groups $G$ with a random minimal generating set, the number of word-differences and the number of states of $W$ seems to grow moderately quickly with $|G|$. I haven't investigated this seriously, but maybe something like $O(\sqrt{|G|})$ for the number of states of $W$.


But the symmetric group $S\_p$ on generators $\{(1,2),(2,3),\ldots,(p-1,p)\}$ is an exception, and I think the reason for this is that $S\_p$ is a Coxeter group on these generators, and in general Coxeter groups (finite and infinite) are automatic and the algorithms run quickly on them. (There is a nice theoretical description of the language of $W$.) In fact the numbers of word-differences and states of $W$ both grow quadratically with $p$. If you try $S\_p$ on a difference generating set then, as you observed, they don't behave so nicely.


In general, the algorithms use an ordered monoid generating set $X$ of $G$, and the performance can vary considerably with $X$ and even occasionally with the chosen ordering of $X$. It is hard to predict which will be the optimal generating set, and it is not always one of minimal size (we saw that with the examples $S\_p$). For example, with a Fibonacci group, it is much better to use the generators in the defining presentation than to reduce it to a $2$-generator group. So I cannot answer your question about how to choose the ordering - you just have to experiment.


