Reference. Weighted NetKAT: A Programming Language for Quantitative Network Verification
We introduce weighted NetKAT, a domain-specific language for modeling and verifying quantitative quantitative network properties. The language is parametric on a semiring , enabling the treatment of a wide range of quantities in a uniform way. We provide a denotational semantics and an equivalent operational semantics, the latter based on a novel model of weighted NetKAT automata ( WNKA ) capturing the stateful behavior of our language. With WNKA , we obtain a class of generic decision procedures for reasoning about quantitative safety and reachability in a fully automatic way, even in the presence of possibly unbounded iteration. We demonstrate the applicability of our framework in a case study using Internet2’s Abilene network as the underlying topology.
Cite
Cited by (2)
A Fast Quantitative Analyzer for NetKAT lu-2026-a
When designing a network, engineers must navigate trade-offs (e.g., one topology offers more aggregate bandwidth, another lower latency or better resilience) that demand reasoning about quantitative properties. We present a fast analyzer for quantitative network properties based on weighted NetKAT (wNetKAT), a domain-specific language that provides a semantic foundation for quantitative reasoning by modeling network behavior using weights drawn from a semiring. At the core of our development is the design of a symbolic data structure – weighted symbolic packet programs (wSPPs) – that compactly represent the semantics of weighted policies, for which a direct implementation would be intractable. We show how to compute all policy constructs symbolically; unsurprisingly, the crux is Kleene star, for which we design a tailored algorithm. We further develop trace-carrying Pareto semirings, which compute multi-objective frontiers together with the network paths that realize them. We formalize the development in Lean and provide an optimized Rust implementation. Being parametric on a semiring, our implementation covers both classical and quantitative analyses: we show that it is competitive with KATch, a heavily optimized Boolean-reachability verifier, and orders of magnitude faster than McNetKAT and Storm on probabilistic analyses. A case study comparing Fat-tree and Jellyfish data-center topologies shows the framework supports multi-objective design-time analysis.
SMT-Based Active Learning of Weighted Automata ferreira-2026-smt
We present an SMT-based active learning algorithm for nondeterministic weighted automata (WFAs) as a practical and robust alternative to Hankel/-style methods. Our algorithm is parametric in a given semiring and, if it terminates, guaranteed to produce minimal WFAs. We prove partial correctness and provide a sufficient termination condition, which in particular implies termination for all finite semirings. Our extensive experimental evaluation shows that our algorithm is capable of learning numerous minimal WFAs over both finite and infinite semirings, vastly outperforms a naive baseline, and is competitive with a state-of-the-art algorithm while producing significantly smaller automata and requiring less interaction with the teacher.
Cites 40 works (6 here)
With notes (6)
Active Learning of Symbolic NetKAT Automata moeller-2025-active
NetKAT is a domain-specific programming language and logic that has been successfully used to specify and verify the behavior of packet-switched networks. This paper develops techniques for automatically learning NetKAT models of unknown networks using active learning. Prior work has explored active learning for a wide range of automata (e.g., deterministic, register, Büchi, timed etc.) and also developed applications, such as validating implementations of network protocols. We present algorithms for learning different types of NetKAT automata, including symbolic automata proposed in recent work. We prove the soundness of these algorithms, build a prototype implementation, and evaluate it on a standard benchmark. Our results highlight the applicability of symbolic NetKAT learning for realistic network configurations and topologies.
Weighted GKAT: Completeness and Complexity vankoevering-2025-weighted
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.
Guarded Kleene algebra with tests: verification of uninterpreted programs in nearly linear time smolka-2019-guarded
Guarded Kleene Algebra with Tests (GKAT) is a variation on Kleene Algebra with Tests (KAT) that arises by restricting the union (+) and iteration (*) operations from KAT to predicate-guarded versions. We develop the (co)algebraic theory of GKAT and show how it can be efficiently used to reason about imperative programs. In contrast to KAT, whose equational theory is PSPACE-complete, we show that the equational theory of GKAT is (almost) linear time. We also provide a full Kleene theorem and prove completeness for an analogue of Salomaa’s axiomatization of Kleene Algebra.
Probabilistic NetKAT foster-2016-probabilistic
Algebra-coalgebra duality in brzozowski’s minimization algorithm bonchi-2014-algebra
We give a new presentation of Brzozowski’s algorithm to minimize finite automata using elementary facts from universal algebra and coalgebra and building on earlier work by Arbib and Manes on a categorical presentation of Kalman duality between reachability and observability. This leads to a simple proof of its correctness and opens the door to further generalizations. Notably, we derive algorithms to obtain minimal language equivalent automata from Moore nondeterministic and weighted automata.
Kleene algebra with tests kozen1997kleene
We introduce Kleene algebra with tests, an equational system for manipulating programs. We give a purely equational proof, using Kleene algebra with tests and commutativity conditions, of the following classical result: every while program can be simulated by a while program with at most one while loop. The proof illustrates the use of Kleene algebra with tests and commutativity conditions in program equivalence proofs.
External (34)
- NetKAT (Google implementation) (2025)
- Galois internship round 2: A second summer intern experience (2025)
- KATch: A Fast Symbolic Verifier for NetKAT (2024)
- Completeness of Finitely Weighted Kleene Algebra with Tests (2024)
- Kleene Algebra With Tests for Weighted Programs (2023)
- Guarded NetKAT: Soundness, partial-completeness, decidability (2023)
- SwitchV (2022)
- Weighted programming: a programming paradigm for specifying mathematical models (2022)
- Cost InterNetKAT: Basics of Algebraic Network Routing (PhD thesis) (2021)
- What's decidable about weighted automata? (2020)
- Validating datacenters at scale (2019)
- Scalable verification of probabilistic networks (2019)
- Cantor meets Scott: semantic foundations for probabilistic networks (2017)
- WNetKAT: A weighted SDN programming and verification language (2016)
- A Coalgebraic Decision Procedure for NetKAT (2015)
- NetKAT (2014)
- A Core Quantitative Coeffect Calculus (2014)
- SDX (2014)
- B4 (2013)
- Algebraic Systems and Pushdown Automata (2011)
- Noncommutative Rational Series with Applications (2010)
- Weighted Automata Algorithms (2009)
- Semirings and Formal Power Series (2009)
- Provenance semirings (2007)
- Metarouting (2005)
- An algebraic theory of dynamic network routing (2005)
- Network calculus: a theory of deterministic queuing systems for the Internet (2001)
- Partially-Ordered Semirings (1999)
- Some consequences of a Fatou property of the tropical semiring (1994)
- Matrix Iteration Theories (1993)
- The equality problem for rational series with multiplicities in the tropical semiring is undecidable (1992)
- On limits in complete semirings (1992)
- A categorical approach to probability theory (1982)
- Regular expressions and the equivalence of programs (1969)