Primitive Recursive Presentations of Transducers and their Products

Abstract. Methods for specifying Moore type state machines (trans-ducers) abstractly via primitive recursive string functions are discussed. The method is mostly of interest as a concise and convenient way of working with the complex state systems found in computer programming and engineering, but a short section indicates connections to algebraic automata theory and the theorem of Krohn and Rhodes. The techniques are shown to allow concise denition of system architectures and the compositional construction of parallel and concurrent systems