Automating the Analysis of Quantitative Automata with QuAK

Marek Chalupa, Thomas A. Henzinger, Nicolas Mazzocchi, N. Ege Saraç · 2025

Read Automating the Analysis of Quantitative Automata with QuAK by Marek Chalupa, Thomas A. Henzinger, Nicolas Mazzocchi, N. Ege Saraç (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-2501-16088.txt.

Introduction

Marek Chalupa, Thomas Henzinger, Nicolas Mazzocchi, and N Ege Saraç present a software kit for quantitative automata, in a paper published in 2025. Such automata go beyond yes-or-no acceptance: each run earns a number, built from weighted steps. They model costs, energy, and quality in computer systems. Theory had outrun tools until a first kit, QuAK, appeared recently.

The paper explains the kit's design and upgrades it. Most tasks reduce to two core problems: checking whether one automaton's values fit inside another's, and finding the best value an automaton can reach. The upgrades return an example word that proves each answer, and add a method that splits safety from liveness even for nondeterministic machines. The authors aim to make quantitative checks a routine part of system design.

Catalog record

CREATORMarek Chalupa, Thomas A. Henzinger, Nicolas Mazzocchi, N. Ege Saraç
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16088

Browse the full library · About the Tower of Babel

Full text

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

Automating the Analysis of Quantitative Automata with QuAK Thanks: This work was supported in part by the ERC-2020-AdG 101020093. Marek Chalupa, Thomas A. Henzinger, Nicolas Mazzocchi, N. Ege Saraç Abstract Quantitative automata model beyond-boolean aspects of systems: every execution is mapped to a real number by incorporating weighted transitions and value functions that generalize acceptance conditions of boolean ω \omega -automata. Despite the theoretical advances in systems analysis through quantitative automata, the first comprehensive software tool for quantitative automata (Quantitative Automata Kit, or QuAK) was developed only recently. QuAK implements algorithms for solving standard decision problems, e.g., emptiness and universality, as well as constructions for safety and liveness of quantitative automata. We present the architecture of QuAK, which reflects that all of these problems reduce to either checking inclusion between two quantitative automata or computing the highest value achievable by an automaton—its so-called top value. We improve QuAK by extending these two algorithms with an option to return, alongside their results, an ultimately periodic word witnessing the algorithm’s output, as well as implementing a new safety-liveness decomposition algorithm that can handle nondeterministic automata, making QuAK more informative and capable. 1 Introduction Traditional system behavior analysis categorizes system behaviors as correct or incorrect. However, modern systems require more nuanced approaches to address performance and robustness criteria. Quantitative automata generalize boolean \omega -automata by adding rational-valued weights to their transitions and using value functions (instead of acceptance conditions) that accumulate infinite weight sequences into single values. Common value functions include {\mathsf{Inf}} , {\mathsf{Sup}} , {\mathsf{LimInf}} , and {\mathsf{LimSup}} (respectively generalizing safety, reachability, co-Büchi and Büchi acceptance conditions), as well as {\mathsf{DSum}} (discounted sum), {\mathsf{LimInfAvg}} , and {\mathsf{LimSupAvg}} (limit average a.k.a. mean payoff). Decision problems for boolean automata extend naturally to quantitative automata. For example, a quantitative automaton \mathcal{A} is nonempty with respect to a rational number v iff \mathcal{A} maps some infinite word w to a value at least v [ 13 ] . These problems are closely related to game theory [ 21 ] and enable reasoning about quantitative system aspects. Although quantitative automata have been extensively studied from a theoretical perspective [ 16 , 5 , 8 , 34 , 35 , 4 , 26 , 24 , 25 , 7 ] and these works could significantly impact their practical verification, until recently, there was no general software tool for their analysis. Quantitative Automata Kit (QuAK) [ 11 ] is the first general tool for quantitative automata analysis. It currently supports several automaton types ( {\mathsf{Inf}} , {\mathsf{Sup}} , {\mathsf{LimInf}} , {\mathsf{LimSup}} , {\mathsf{LimInfAvg}} , {\mathsf{LimSupAvg}} ) and provides decision procedures for fundamental problems such as emptiness, universality, inclusion, and safety. We present an improved version of QuAK: (i) the safety-liveness decompositions are extended to handle nondeterministic automata, and (ii) the inclusion and top value algorithms are extended with capabilities to return a witness—an ultimately periodic word explaining the algorithm’s output. For checking inclusion, i.e., whether \mathcal{A}(w)\leq\mathcal{B}(w) for all words w , the witness \hat{w} is a word such that \mathcal{A}(\hat{w})>\mathcal{B}(\hat{w}) . For computing top value, i.e., \top_{\mathcal{A}}=\sup_{w\in\Sigma^{\omega}}\mathcal{A}(w) , the witness \widehat{w} is a word such that \mathcal{A}(\hat{w})=\top_{\mathcal{A}} . Since all the other procedures are reduced to either inclusion checking or top value computation, these extensions significantly improve QuAK’s informativeness for analyzing quantitative automata. Several approaches extend system modeling beyond boolean aspects. One uses multi-valued truth domains [ 9 , 15 ] , while another relies on weighted automata [ 36 ] , where numerical weights are assigned to transitions and accumulated via semiring operations. Tools such as Vaucanson [ 32 ] , Vcsn [ 18 ] , and Awali [ 31 ] support weighted automata analysis. Other approaches address digital-analog interactions [ 2 , 1 , 22 ] , with tools like UPPAAL [ 30 ] and HyTech [ 23 ] . Signal temporal logic [ 33 ] allows reasoning about specification satisfaction degrees, as implemented in Breach [ 19 ] , S-TaLiRo [ 3 ] , and RTAMT [ 37 ] . Probabilistic verification handles uncertainties, as implemented in PRISM [ 29 ] and STORM [ 17 ] . 2 Quantitative Automata Let \Sigma be a finite alphabet of letters. We denote by \Sigma^{*} (resp. \Sigma^{\omega} ) the set of all finite (resp. infinite) words over \Sigma . For w\in\Sigma^{\omega} and u\in\Sigma^{*} , we write u\prec w when u is a prefix of w . A value domain \mathbb{D} is a nontrivial complete lattice. A quantitative property is a total function \varPhi:\Sigma^{\omega}\to\mathbb{D} . We study quantitative automata, which define a subset of quantitative properties on totally-ordered value domains. Formally, a nondeterministic quantitative automaton (or simply an automaton ) is a tuple \mathcal{A}=(\Sigma,Q,s,\delta) where \Sigma is a finite alphabet, Q is a finite nonempty set of states, s\in Q is the initial state, and \delta\colon Q\times\Sigma\to 2^{\mathbb{Q}\times Q} is a finite transition function over weight-state pairs [ 13 ] . A transition is a tuple (q,\sigma,x,q^{\prime})\in Q\times\Sigma\times\mathbb{Q}\times Q such that (x,q^{\prime})\in\delta(q,\sigma) , denoted q\xrightarrow{\sigma:x}q^{\prime} . The weight of a transition t=(q,\sigma,x,q^{\prime}) is denoted by \gamma(t)=x . An automaton \mathcal{A} is deterministic when |\delta(q,a)|=1 for every q\in Q and a\in\Sigma , and it is total (a.k.a. complete ) when |\delta(q,a)|\geq 1 for every q\in Q and a\in\Sigma . We require quantitative automata to be total. A run of \mathcal{A} on an infinite word w=a_{0}a_{1}\ldots is an infinite sequence \rho=q_{0}\xrightarrow{a_{0}:x_{0}}q_{1}\xrightarrow{a_{1}:x_{1}}q_{2}\ldots of transitions where q_{0}=s and (x_{i},q_{i+1})\in\delta(q_{i},a_{i}) for each integer i\geq 0 . Since each transition has a weight, a run \rho=t_{0}t_{1}\ldots produces an infinite sequence \gamma(\rho)=\gamma(t_{0})\gamma(t_{1})\ldots of weights. A value function {\mathsf{Val}}:\mathbb{Q}^{\omega}\to\mathbb{R} maps infinite weight sequences to real values. A {\mathsf{Val}} -automaton is a quantitative automaton equipped with the value function {\mathsf{Val}} , i.e., where each run \rho is mapped to the value obtained by applying {\mathsf{Val}} to its weight sequence \gamma(\rho) . Given a {\mathsf{Val}} -automaton \mathcal{A} , the value of an infinite word w is \mathcal{A}(w)=\sup\{{\mathsf{Val}}(\gamma(\rho))\;|\;\text{$\rho$ is a run of $\mathcal{A}$ on $w$}\} . The top value of an automaton \mathcal{A} is \top_{\mathcal{A}}=\sup_{w\in\Sigma^{\omega}}\mathcal{A}(w) , and its bottom value is \bot_{\mathcal{A}}=\inf_{w\in\Sigma^{\omega}}\mathcal{A}(w) . We consider the below value functions over an infinite sequence x=x_{0}x_{1}\ldots of rational weights. • \displaystyle{\mathsf{Inf}}(x)=\inf\limits_{n\geq 0}x_{n} • \displaystyle{\mathsf{LimInf}}(x)=\liminf\limits_{n\to\infty}x_{n} • \displaystyle{\mathsf{LimInfAvg}}(x)=\liminf\limits_{n\to\infty}\left(\frac{1}{n}\sum_{i=0}^{n-1}x_{i}\right) • \displaystyle{\mathsf{Sup}}(x)=\sup\limits_{n\geq 0}x_{n} • \displaystyle{\mathsf{LimSup}}(x)=\limsup\limits_{n\to\infty}x_{n} • \displaystyle{\mathsf{LimSupAvg}}(x)=\limsup\limits_{n\to\infty}\left(\frac{1}{n}\sum_{i=0}^{n-1}x_{i}\right) • For a discount factor \displaystyle\lambda\in\mathbb{Q}\cap(0,1) , {\mathsf{DSum}}_{\lambda}(x)=\sum_{i\geq 0}\lambda^{i}x_{i} The automaton \mathcal{A} in Figure 1 shows a {\mathsf{LimInfAvg}} automaton modeling the long-term average power consumption of a device with two operating modes. ( \mathcal{A} ) q_{0} q_{1} q_{2} q_{3} \textit{hi}:6 \textit{lo}:3 \Sigma:6 \textit{lo}:2 \textit{hi}:5 \textit{lo}:3 \Sigma:4 ( \mathcal{B} ) q_{0} q_{1} q \textit{hi}:6 \textit{lo}:4 \Sigma:6 \Sigma:4 ( \mathcal{C} ) q_{0} q_{1} q_{2} q_{3} \textit{hi}:6 \textit{lo}:3 \Sigma:6 \textit{lo}:2 \textit{hi}:5 \textit{lo}:3 \Sigma:4 q^{\prime}_{1} q^{\prime}_{3} q_{\bot} \textit{hi}:6 \textit{hi}:6 \textit{hi}:6 \textit{hi}:6 \Sigma:2 \Sigma:2 \Sigma:2 Figure 1 : A nondeterministic {\mathsf{LimInfAvg}} -automaton \mathcal{A} over the alphabet \Sigma=\{\textit{hi},\textit{lo}\} , modeling the power consumption of a device where starting with high-power mode is not reversible, its safety closure \mathcal{B} , and its liveness component \mathcal{C} in a corresponding decomposition [ 6 ] . Quantitative Automata Problems We describe the standard decision problems of quantitative automata as well as the problems related to their safety and liveness. The complexity results are summarized in Table 1 . An automaton \mathcal{A} is nonempty (resp. universal ) with respect to a

Read the complete text