|Abstract of Paper|
Separation Results for Rebound Automata
by Holger Petersen
We show that the class of languages accepted by nondeterministic two-dimensional rebound automata properly contains the class of languages accepted by deterministic rebound automata. Further we separate the class of languages accepted by deterministic one-way one counter automata from the languages accepted by rebound automata, strengthening previous results. The language separating these classes is in fact deterministic linear, which improves the known result that there is a context-free language not accepted by rebound automata.