Skip to main content
4 of 4
added 34 characters in body
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

This is an answer for the special case of a free monoid where this is somehow a different language for standard facts about transducers and automata although I can’t write an exact reference in this language. I strongly suspect that this case is indeed special and will not generalize but this is too long for a comment so here goes.

Let $F(X)$ denote the free monoid on a set $X$. Given an action of $F(X)$ on the right of a set $A$, we can associate to each $a\in A$ a homography $f_a\colon F(X)\to F(A)$ as follows. Put $f_a(1)=1$ and put $f_a(x_1\cdots x_n)$ equal to the concatenation of the list $a,ax_1,ax_1x_2,\cdots, ax_1x_2\cdots x_{n-1}$ of elements of $A$ for $n>0$. Note the mapping $a\mapsto f_a$ is injective since $f_a(x)=a$ for any $x\in X$. Also one easily checks $f_{aw}$ is the shift of $f_a$ by $w$ as $f_a(ww’)=f_a(w)f_{aw}(w’)$ by construction.

I don’t know if something can be done for $W$ a free commutative monoid on more than one generator.

Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186