ABSTRACT
This chapter discusses deep pushdown automata, which represent modified versions of ordinary pushdown automata. Specifically, these modified versions can rewrite non-input symbols deeper than on the very top of their pushdown lists. The chapter formalizes discontinuous computation by grammars and automata working with unordered strings. It continues with the discussion of models that define unodered strings. It covers permutation grammars, which are based upon classical grammars that generate unordered strings. Pushdown automata discussed in this section represent language-accepting models based upon slightly generalized stack structures, which can be modified deeper than on their tops. As opposed to the ordinary versions of pushdown automata, which can only expand the stack tops, these generalized versions can jump deeper into their stacks or, speaking in terms of automata theory, pushdown lists and make expansions therein, hence their name—deep pushdown automata.
