Consider a pair $s=(s_0,s_1)$ of bit-strings (strings of 0s and 1s). Let $s$ act on a bit-string $b$ by replacing every $0$ in $b$ by $s_0$ and every $1$ in $b$ by $s_1$. Then the set $S$ of all such 'substitutions' forms a semigroup.
I am interested in finding out various properties of this semigroup. Surely the structure this semigroup has been studied before. Any pointers?
Some questions about this semigroup:
- Are there any other automorphisms except for the identity and interchanging 0 and 1? (Probably no, but how do you prove this?)
- Is there a proper subsemigroup of $S$ isomorphic to $S$?questions?
- What are the commutative subsemigroups? One example is the semigroup of substitutions of the form (00…0,11…1) which is isomorphic to $(\mathbf{N}^2,\cdot)$.
- The cancellation property does not hold in general. Is there a subsemigroup for which it holds?
Any information, pointers to papers, websites, … are welcome.