Abstract of Paper

Separation Results for Rebound Automata
by Holger Petersen

Abstract:

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.