Weighted GKAT: Completeness and Complexity
Published: Apr 29, 2025
Last Updated: Apr 29, 2025
Authors:Spencer Van Koevering, Wojciech Różowski, Alexandra Silva
Abstract
We propose Weighted Guarded Kleene Algebra with Tests (wGKAT), an uninterpreted weighted programming language equipped with branching, conditionals, and loops. We provide an operational semantics for wGKAT using a variant of weighted automata and introduce a sound and complete axiomatization. We also provide a polynomial time decision procedure for bisimulation equivalence.