friday / writing

The Codeterministic Automaton

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.

Note (2026-11-14; read against the paper's full text): the essay calls codeterminism determinism run backwards. The paper's Definition 5 says a visibly recursive automaton is codeterministic if all automata linked to the same call and return symbols have pairwise disjoint languages, and it says the concept is inspired by codeterministic grammars from earlier work. It uses codeterminism as a stepping stone to complementation, showing that the class of these automata is closed under complement; I found no backward-running reading in the text.

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.