Weighted GKAT: Completeness and Complexity

Spencer Van Koevering, Wojciech Różowski, Alexandra Silva · 2025

Read Weighted GKAT: Completeness and Complexity by Spencer Van Koevering, Wojciech Różowski, Alexandra Silva (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20385.txt.

Introduction

Spencer Van Koevering and co-authors add weights to a program logic in 2025. Guarded Kleene algebra with tests is a tidy language for programs with branches and loops. The weighted version tracks costs or counts as programs run, not just yes or no outcomes. That suits programs where totals matter, such as resource use.

The authors give the language a running model based on weighted automata. They then supply a full set of proof rules that match the model exactly. A fast method decides when two programs act the same in all cases. The package gives weighted programs the same firm base their plain cousins enjoy.

Catalog record

CREATORSpencer Van Koevering, Wojciech Różowski, Alexandra Silva
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20385

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Weighted GKAT: Completeness and Complexity 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. Cornell University, United States of America and https://spencerkoevering.github.io/ [email protected]://orcid.org/0009-0008-5026-8060Partially supported by a Cornell Bowers CIS Deans Excellence Fellowship.University College London, United Kingdom and https://wkrozowski.github.io/ [email protected]://orcid.org/0000-0002-8241-7277Partially supported by ERC grant Autoprobe (grant agreement 101002697). Cornell University, United States of America and https://alexandrasilva.org/ [email protected]://orcid.org/0000-0001-5014-9784Partially supported by ONR grant N68335-22-C-0411, ERC grant 101002697, and a Royal Society Wolfson fellowship. {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003753¡/concept_id¿ ¡concept_desc¿Theory of computation Models of computation¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Models of computation keywords Weighted Programming, Automata, Axiomatization, Decision Procedure † † runningauthor: S. Van Koevering, W. Różowski, A. Silva † † copyright: Spencer Van Koevering, Wojciech Różowski, and Alexandra Silva † † editors: Keren Censor-Hillel, Fabrizio Grandoni, Joel Ouaknine, and Gabriele Puppis † † event-title: 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) † † event-shorttitle: ICALP 2025 † † event-acronym: ICALP † † year: 2025 † † event-date: July 8–11, 2025 † † event-location: Aarhus, Denmark † † series-volume: 334 † † articleno: 160 1 Introduction Weighted programming is a recently introduced paradigm [ 2 ] in which computational branches of programs are associated with quantities. For example, the program e\,{\vphantom{{\oplus}}}_{\frac{2}{5}}{\oplus}_{\frac{3}{5}}\,f does e with weight \frac{2}{5} and f with weight \frac{3}{5} . Semantically, each branch is executed, its results scaled, and then results of different branches added. If we were to interpret weights as probabilities and use addition of real numbers, then the above example would be a classic randomized program: a biased coin flip. If we interpret the weights as costs rather than a probability, and addition as minimum rather than traditional addition, then e\,{\vphantom{{\oplus}}}_{\frac{2}{5}}{\oplus}_{\frac{3}{5}}\,f would model selecting the cheapest resulting branch and be well suited for optimization problems. Weighted programs can model problems from a variety of domains, including optimization, model checking, and combinatorics [ 2 ] . However, reasoning about their behavior is difficult as different interpretations of the weights lead to different properties of the programs and their semantics, impacting, for instance, whether the equivalence of weighted programs is decidable. In this paper, we propose an algebraic approach to reason about equivalence of weighted programs and devise a decision procedure which applies to a large class of weights. The starting point of our development is Guarded Kleene Algebra with Tests ( GKAT ) [ 30 ] , an algebraic framework for reasoning about equivalence of uninterpreted imperative programs. Its equational axiomatization offers a simple framework for deductive reasoning, and it also has a decision procedure. We propose and axiomatize a GKAT -inspired weighted programming language, wGKAT , which enables reasoning about the equivalence of deterministic, uninterpreted programs with weighted branching . We design this language with the goals of offering an equational axiomatization and a polynomial-time decision procedure for the equivalence of expressions, both derived uniformly for a broad class of weights. One of the primary challenges we address is identifying a suitable class of semirings which is sufficient to prove that bisimulation is a complete proof technique for behavioural equivalence and, moreover, to define a operational semantics of loops. Using this class of semirings we were able to generalize traditional arguments for soundness and completeness from process algebra to our setting [ 28 ] . Another challenge is the decidability of equivalence for weighted programs, which hinges on properties of the semiring as well. We leverage existing work on monoid labeled transition systems to design the operational semantics and establish that equivalence up to bisimilarity is decidable for wGKAT . Our work was developed concurrently with another weighted variant of Kleene Algebra with Tests, called Kleene Algebra with Weights and Tests ( KAWT ) [ 29 ] . KAWT lacks a decision procedure and admits only a restrictive class of weights. The key difference in our work that enables us to significantly enlarge the class of weights we can consider is that KAWT extends KAT directly whereas our starting point is GKAT , the deterministic fragment of KAT . This is what allows us to offer a decision procedure and a sound and complete axiomatization: by carefully selecting the class of weights we retain the general road map to soundness and completeness of GKAT as well as the efficient decision procedure. In a nutshell, our contributions are as follows. 1. We propose a weighted version of GKAT and equip it with an operational semantics using a variant of weighted automata ( Sections 2 and 3 ). 2. We identify a class of semirings for which the semantics of weighted loops can be computed when considering bisimulation equivalence ( Section 3.2 ). 3. We axiomatize bisimulation equivalence for wGKAT and provide a proof soundness ( Section 4 ) and a proof of completeness ( Section 5 ). 4. We design a decision procedure for bisimilarity which runs in O(n^{3}\log^{2}n) time if the number of tests is fixed, where n is the size of the programs considered ( Section 6 ). We conclude and discuss directions for future work in Section 8 . 2 Syntax \displaystyle e,f\in\textbf{{Exp}} \displaystyle\coloneq \displaystyle\;\textbf{p}\in\textbf{{Act}} do p \displaystyle\mid \displaystyle b\in\textbf{{BExp}} assert b \displaystyle\mid \displaystyle e+_{b}f \displaystyle\text{if }\textbf{b}\text{ do }e\text{ else do }f \displaystyle\mid \displaystyle e;f \displaystyle\text{do }e\text{ then do }f \displaystyle\mid \displaystyle e^{(b)} \displaystyle\text{while }\textbf{b}\text{ do }e \displaystyle\mid \displaystyle v\in\textbf{{Out}} return v \displaystyle\mid \displaystyle e\,{\vphantom{{\oplus}}}_{r}{\oplus}_{s}\,f \displaystyle\text{do }e\text{ with weight }\textbf{r}\text{ and }f\text{ with weight }\textbf{s} Figure 1 : Syntax of wGKAT In this section, we introduce the syntax of our language and examples on how to use it to model simple quantitative programs. The syntax of wGKAT ( Figure 1 ) is two-sorted consisting of the set Exp of expressions containing a sort BExp of Boolean expressions also called tests. Intuitively, Exp represents the overall syntax of weighted programs, while BExp is used to specify assertions, as well as conditional expressions appearing in the scope of if-then-else and while constructs. Given a finite set T of primitive tests , we define BExp , the grammar of tests, to be given by the following: b,c\in\textbf{{BExp}}\coloneq\mymathbb{0}\mid\mymathbb{1}\mid t\in T\mid\bar{b}\mid b+c\mid bc In the above, \mymathbb{0} and \mymathbb{1} respectively represent false and true, \bar{\cdot} denotes negation, + represents disjunction and juxtaposition is conjunction. We will write \equiv_{\textsf{BA}} to denote Boolean equivalence in BExp . Logical entailment defines a preorder given by b\leq_{\textsf{BA}}c\iff b+c\equiv_{\textsf{BA}}c . The quotient of BExp by the relation \equiv_{\textsf{BA}} , denoted by {\textbf{{BExp}}}/{\equiv_{\textsf{BA}}} is in one-to-one correspondence with the Boolean Algebra freely generated by the set T . The entailment [b]_{\equiv_{\textsf{BA}}}\leq[c]_{\equiv_{\textsf{BA}}}\iff b\leq_{\textsf{BA}}c defines a partial order on {\textbf{{BExp}}}/{\equiv_{\textsf{BA}}} . The minimal nonzero elements in that order are called atoms and we will write At for the set of them. The syntax of wGKAT is parametric on two fixed sets: Act of uninterpreted program actions and Out of possible return values. The first five constructs in Figure 1 , namely uninterpreted program actions, Boolean assertions, conditionals, sequential composition and while loops capture

Read the complete text