An Algebraic Semantic Framework for Nondeterministic ComputationResearch Paper
Zheng, Zheng, Wang and Huang, in An Algebraic Semantic Framework for Nondeterministic Computation (July 2026, a STOC 2027 submission), propose to study nondeterminism through algebraic structure attached to tape symbols: two nondeterministic branches are regarded as genuinely independent when the algebraic numbers that encode them are linearly independent…