In order to compare primitive recursive functions and transductions defined by automata in a natural way independent of encodings, we generalize the Grzegorczyk hierarchy, the recursion number hierarchy and the loop hierarchy from arithmetical to wordfunctions. We observe several differences between the arithmetical and the non-arithmetical theory. By means of turingmachines and generalized sequential machines all inclusion problems for the function classes of these hierarchies are solved. Transductions and languages defined by automata are classified within these hierarchies. Moreover, we introduce and study primitive recursive transformations between different monoids.
展开▼
