Descriptional complexity of two-way pushdown automata with restricted head reversals (Q443747): Difference between revisions

While in the case of finite automata, the possibility of moving the input head in both directions does not increase the recognition power, in the case of pushdown automata the models resulting by adding this capability, called two-way pushdown automata (2PDAs), are strictly more powerful than standard one-way pushdown automata (PDAs) that, as is well known, characterize the class of context-free languages. For instance, it is not difficult to write an algorithm which uses a deterministic 2PDA to recognize the language \(\{a^nb^nc^n\mid n\geq 0\}\), but, as is well known, such a language cannot be accepted by any PDA, even making use of nondeterminism. Actually, up to now, the computational power of 2PDAs has not been clearly identified. In particular, it is unknown whether these models are equivalent to linear bounded automata and whether the nondeterministic and the deterministic versions have the same computational power. The paper investigates, from a descriptional complexity point of view, 2PDAs which are allowed to make a constant number (i.e., not dependent on the input length) of input head reversals on each string. The authors show that under this restriction, 2PDAs have some interesting common properties with standard PDAs [the first author and the reviewer, Lect. Notes Comput. Sci. 4588, 312--323 (2007; Zbl 1202.68233); Inf. Comput. 227, 1--20 (2013; Zbl 1358.68173)]: -- In the case of (letter- and word-) bounded languages, the number of pushdown turns can be reduced to a constant by exponentially increasing the size of the description. -- If the restriction to bounded languages is dropped, then the size of the description of the resulting devices cannot be bounded by any recursive function. Further results are given, by restricting to deterministic 2PDAs. Not so many papers are devoted to the study of 2PDAs and, as already mentioned, fundamental questions about these devices are still open. This paper gives new contributions to this area where, as pointed out in the final section, many questions are open and should be investigated in the future.