Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

Question

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs are not equivalent in power to nondeterministic PDAs.

However, all CFLs are decidable, and in this case, any deterministic TM is equivalent in power to a nondeterministic TM.

Now, this is a large gap - what is the smallest language "above" CFLs that is closed under nondeterminism?

Answer 1

The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of

1. a read-only input tape, surrounded by endmarkers,
2. a finite state control,
3. a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
4. a stack

In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, and Computation (1st ed.) we find:

Theorem 14.1 The following are equivalent for $S(n)\geq\log n$.

1. $L$ is accepted by a deterministic $S(n)$-AuxPDA
2. $L$ is accepted by a nondeterministic $S(n)$-AuxPDA
3. $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.

with the surprising:

Corollary $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.

Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking.

---

The above is a copy of large parts of an answer to another question. So in which sense does it answers the current question? It is not the smallest imaginable class that contains $\mathsf{CFL}$ and is closed under nondeterminism. But it is a very well known class (i.e. $\mathsf P$) and a natural machine model, which has been studied thoroughly in the past, and is still studied today (with an additional runtime restriction) in the context of LogCFL. Indeed, LogCFL is also closed under nondeterminism and is closer than $\mathsf P$ to $\mathsf{CFL}$, proving my point that the above (i.e. $\mathsf P$ = $\log n$-AuxPDA) is not the smallest imaginable class of this kind.