Storage Products and Linear Control of Derivations
Christian Wartena · Theory of Computing Systems · 2007
Various automata using certain kinds of tuples of storages are defined in the literature. In this paper we investigate some possibilities to define such storages independently of automata by a restricted type of product on storages, called concatenation. It is shown that there is a strong relation between automata with concatenated pushdowns and restricted classes of linear controlled grammars. Using this result, some relations between hierarchies of automata with an ascending number of concatenated pushdowns and some well-known hierarchies of controlled grammars follow naturally.