Two-way automata with more than one storage medium (Q1083206)

This paper is concerned with the computational power of two-way automata with more than one subrecursive storage medium. Two-way automata with a stack (a nonerasing stack or a pushdown store, respectively) and an arbitrary number of checking stacks are of special interest. They are able to accept exactly those sets which are elementary in the sense of Kalmár. If the number of checking stacks is fixed, then the computational power of the corresponding restricted classes of automata can also be characterized in terms of time and space complexity classes.