  We study versions of Kleene algebra with dynamic tests, that is, extensions
of Kleene algebra with domain and antidomain operators. We show that Kleene
algebras with tests and Propositional dynamic logic correspond to special cases
of the dynamic test framework. In particular, we establish completeness results
with respect to relational models and guarded-language models, and we show that
two prominent classes of Kleene algebras with dynamic tests have an
EXPTIME-complete equational theory.

Logic in Computer Science