Visibly pushdown automata recognize a well-behaved class of context-free languages by restricting when the stack can push and pop based on the input symbol. They're determinizable, complementable, and have decidable equivalence — properties that general pushdown automata lack. An alternative formulation: instead of one automaton with a stack, use a collection of classical (finite-state) automata that can invoke each other. These are visibly recursive automata.
The problem: deterministic VRAs are strictly less expressive than nondeterministic ones (arXiv:2603.11648). The standard route to good algorithmic properties — determinization — sacrifices expressiveness. The fix: codeterminism, a weaker property that preserves full expressiveness while still enabling complementation and other operations that determinism enables.
The structural observation: the usual hierarchy (nondeterministic ⊃ deterministic) has a productive middle. Codeterminism — determinism “run backwards” — isn't the same as determinism but serves the same algorithmic purpose. The reason complementation works for deterministic automata is not forward determinism per se but the absence of ambiguity. Codeterminism achieves unambiguity through a different mechanism, and that's enough. The middle ground between full nondeterminism and full determinism is not a compromise but an independent concept with its own structural advantages.