1998/12/16 by Peter Hines, Peter M. Hines, Hines, Peter M.
Computer Science · Mathematics · #Category Theory (math.CT) #Cellular Automata and Applications #Computability, Logic, AI Algorithms #F.1.1 #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #cs.LO #f.4.1 #math.CT #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/9812019
21 pages, submitted
arxiv created 1998/12/16 · openalex publication_date 1998/12/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.