Algebras for Deterministic Computation Are Inherently Incomplete

Balder ten Cate, Tobias Kappé

Kleene Algebra with Tests (KAT) provides an elegant algebraic framework for describing non-deterministic finite-state computations. Using a small finite set of non-deterministic pr…