  We consider the structures given by repeatedly generalising the definition of
finite state automata by symmetry considerations, and constructing analogues of
transition monoids at each step. This approach first gives us non-deterministic
automata, then (non-deterministic) two-way automata and bounded Turing machines
--- that is, Turing machines where the read / write head is unable to move past
the end of the input word.
  In the case of two-way automata, the transition monoids generalise to
endomorphism monoids in compact closed categories. These use Girard's
resolution formula (from the Geometry of Interaction representation of linear
logic) to construct the images of singleton words.
  In the case of bounded Turing machines, the transition homomorphism
generalises to a monoid homomorphism from the natural numbers to a monoid
constructed from the union of endomorphism monoids of a compact closed
category, together with an appropriate composition. These use Girard's
execution formula (also from the Geometry of Interaction representation of
linear logic) to construct images of singletons.
