How does a two-way pushdown automaton work?

Question

Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape.

I recently had the question of determining the computational power of two-way PDAs in the Chomsky hierarchy. I don't entirely understand two-way PDAs, but I can see how with the ability to read in both directions on the input, it could handle languages of the form $L=\{0^n 1^n 2^n\}$. I can't say that for sure, but it seems that would make it powerful enough to least handle context-sensitive languages.

This is all a guess because I don't know exactly how they work. Can someone explain the process of how a two-way PDA operates, maybe even on my example?

UPDATE:

The model is a generalization of a pushdown automaton in that two-way motion is allowed on the input tape which is assumed to have endmarkers.

Answer 1

A two-way PDA can accept the canonical context-sensitive language $\{0^{n}1^{n}2^{n} | n \geq 1\}$. Such an automaton could work by checking whether the largest prefix of the form $0^{i}1^{j}$ had $i = j$, using the stack, after which it could empty the stack, and check whether the largest suffix of the form $1^{j}2^{k}$ had $j=k$, again using the stack. So $CFL \subsetneq L(2PDA)$.

In more detail, the 2-way PDA would read from left to right as many 0 symbols as it finds, pushing a 0 onto the stack for each 0 it reads on the input tape. If it reads any 0 symbols and finds a 2 symbol before finding a 1, it crashes. When it gets to a 1, it changes state, and begins reading all the 1 symbols, until it comes to a 2. If it reads a 0 symbol while doing this, it crashes. It pops a 0 symbol from the stack for each 1 it reads on the input tape. If, when it reaches the first 2, the stack is empty, the PDA moves the tape head to the end of the input tape. Otherwise, it crashes. If it encounters any 0s or 1s, it crashes. It then reads the input tape left to right, pushing a 2 for each 2 it reads on the input tape. When it gets to a 1, it switches states and begins reading 1s and popping 2s. If, when it gets to a 0, the stack is empty, the string is accepted.

The machine would crash if the input string weren't a string of 0s, followed by 1s, followed by 2s; and it would have crashed if the longest prefix of 0s and 1s weren't in the canonical CFL $\{0^{n}1^{n}\}$; and it would have crashed if the longest suffix of 1s and 2s weren't in the canonical CFL $\{1^{n}2^{n}\}$. In this case, the ability to rewind the tape allows you to accept languages which are the intersection of CFLs, by essentially stringing PDAs together, and rewinding the tape in between.

Therefore, the languages accepted by two-way PDAs are trivially closed under intersection, a property not shared by languages accepted by regular PDAs.