Formal languages and groups as memory
arXiv:math/0601061
Abstract
We present an exposition of the theory of finite automata augmented with a multiply-only register storing an element of a given monoid or group. Included are a number of new results of a foundational nature. We illustrate our techniques with a group-theoretic interpretation and proof of a key theorem of Chomsky and Schutzenberger from formal language theory.
15 pages, 1 figure, exposition improved, glitches fixed, references and author's contact details updated