💻 computer science

Extending QuAK with Nested Quantitative Automata

This paper extends the Quantitative Automata Kit (QuAK) to support Nested Quantitative Automata by implementing flattening procedures that reduce these more expressive models to standard Quantitative Automata, thereby enabling practical analysis of unbounded properties like average response time through existing decision procedures.

Original authors: Thomas A. Henzinger, Nicolas Mazzocchi, N. Ege Saraç, Harun Yılmaz

Published 2026-05-13

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Thomas A. Henzinger, Nicolas Mazzocchi, N. Ege Saraç, Harun Yılmaz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy call center. Your goal is to ensure the system runs smoothly. In the old days, checking a system was like a simple "Pass/Fail" test: Did the call get answered? Yes or No.

But real life is more complicated. You don't just want to know if a call was answered; you want to know how long it took, or what the average wait time is over a year. This is where "Quantitative Automata" (QAs) come in. They are like smart calculators built into the system that add up weights (like time or cost) as events happen.

The Problem: The "Infinite Wait" Dilemma
The problem with these standard calculators is that they have a limited memory for numbers. They can handle small, fixed amounts of data. But what if a customer waits for 10 minutes? Or 10 hours? Or 10 years?
If a customer waits an arbitrarily long time, the number gets too big for the standard calculator to handle. It's like trying to measure the depth of the ocean with a ruler that only goes up to one foot. You can't measure the deep stuff.

The Solution: The "Manager with Interns" (Nested Automata)
The paper introduces a new, more powerful tool called Nested Quantitative Automata (NQAs).

Think of this as a Manager (the parent automaton) who hires Interns (child automata).

The Manager: Stands at the front desk, watching the infinite stream of calls.
The Interns: Every time a new call comes in (a "request"), the Manager spawns a specific Intern.
The Task: This Intern follows that specific call. They count every second (or step) until the call is finally answered (a "grant").
The Report: Once the call is answered, the Intern stops, writes down the total time they waited, and hands that number back to the Manager.
The Final Score: The Manager collects all these numbers from all the interns over time and calculates the final result, like the "average wait time."

Because each Intern only deals with one call, they can count as high as they need to (even if the wait is huge). The Manager then aggregates these huge numbers into a meaningful average. This solves the "infinite wait" problem that the old calculators couldn't handle.

The Challenge: Making it Work in the Real World
While the math behind this "Manager and Intern" system was proven to work on paper, no one had actually built a software tool to do it. It was like having a brilliant architectural blueprint for a skyscraper but no construction crew to build it.

What This Paper Did: Building the Tool (QuAK)
The authors extended a software tool called QuAK (Quantitative Automata Kit) to actually build and analyze these "Manager and Intern" systems.

Their secret sauce is a process they call "Flattening."
Imagine you have a complex, multi-story building (the Nested Automaton with Managers and Interns). The software takes this complex building and "flattens" it into a single-story, wide-open warehouse (a standard Quantitative Automaton) that the computer already knows how to process.

How it works: The software looks at the Manager's rules and the Interns' tasks and translates them into a single, massive set of instructions that a standard computer can run.
The Catch: Sometimes this "flattened" warehouse is huge and takes a lot of memory to store, but the software is smart enough to know exactly which questions it can answer (like "Is the average wait time under 5 minutes?") without needing to simulate every single second of every single call in real-time.

The Results: Testing the Tool
The team tested their new tool on two types of scenarios:

Response Time: Like the call center example, checking how long requests take to get grants.
Resource Consumption: Like a factory where machines start and stop, and you need to track how much energy or material each machine used before it shut down.

They found that the tool works well for many common cases. However, they also found that when you have too many interns working at the exact same time, or when the tasks are very complex, the "flattened" warehouse gets so big that it slows down the computer. This is a known trade-off: the tool is powerful, but it gets heavy when the system gets too crowded.

In Summary
This paper bridges the gap between theory and practice. It takes a powerful mathematical idea (Nested Quantitative Automata) that allows us to measure complex, unbounded things like average response times, and builds a working software tool (QuAK) that can actually check if a system meets those requirements. It turns a theoretical "Manager with Interns" concept into a real-world verification tool.

Technical Summary: Extending QuAK with Nested Quantitative Automata

Problem Statement

Quantitative automata (QAs) extend finite-state $\omega$ -automata with weighted transitions to specify quantitative system properties, such as average workload or peak memory usage. However, standard QAs are limited by finite weight sets, which prevents them from expressing properties requiring unbounded values, such as average response time. In such scenarios, the delay between a request and a grant can be arbitrarily large, a constraint that finite transition weights cannot capture.

While Nested Quantitative Automata (NQAs) were theoretically introduced to solve this by allowing a parent automaton to spawn child automata that compute unbounded values over finite infixes, NQAs have historically lacked practical tool support. Existing decision procedures for NQAs remained theoretical, leaving a gap between decidability results and automated verification.

Methodology

The authors address this gap by extending QuAK (Quantitative Automata Kit), a software tool for QA analysis, to support NQAs. The core methodology relies on flattening procedures that reduce NQA instances to standard QA instances. This reduction preserves the answers to threshold decision problems (emptiness and universality) without necessarily preserving semantic equivalence between the input NQA and the output QA.

The flattening pipeline, implemented in C++, handles the following algorithmic strategies based on the combination of parent aggregators ( $f$ ) and child aggregators ( $g$ ):

Regular Children ( $g \in \{Min, Max, SumB\}$ ): Since the set of possible return values is finite, the tool guesses the child's return value and verifies it using an obligation-based approach. This involves tracking possible child configurations in parallel and pruning those that cannot reach a final state with the guessed value.
Threshold-Based Bounding ( $f \in \{Sup, LimSup, Inf, LimInf\}, g \in \{Sum+, Sum-\}$ ): For these cases, child return values exceeding a specific threshold $\lambda$ are truncated. This reduces the problem to the bounded $SumB$ case, enabling the regular children construction.
Extremal Parents with Monotonic Children: For emptiness checking with extremal parents ($Sup, LimSup, Inf, LimInf$) and monotonic children, the tool avoids computing exact return values. Instead, it reduces each child invocation to a binary threshold outcome (can the child return a value $\ge \lambda$ ?). This allows for specialized "guess-and-verify" procedures that track only the necessary threshold status, significantly reducing state space compared to general reductions.
Limit-Average with Unbounded Children:
- For $(LimSupAvg, Sum+)$, the tool first checks if child return values can grow unboundedly. If so, emptiness holds trivially; otherwise, it reduces to the bounded $SumB$ case.
- For $(LimInfAvg, Sum-)$ and $(LimSupAvg, Sum-)$, the tool employs a synchronization construction where all active children advance simultaneously, tracking a bounded multiset of active child states.
Silent-Weight Elimination: The flattening process generates QAs with silent weights (transitions that invoke no child). These are eliminated by replacing them with neutral weights (e.g., $-\infty$ for $Sup$) or via path-compression constructions for limit-average objectives.
Antichain-Based Universality: To decide universality, the tool performs an on-the-fly search for counterexample words, using antichains to prune the exploration space. Contexts are enriched with value summaries to handle quantitative bounds alongside reachability.

Key Contributions

Tool Implementation: The first practical implementation of NQA analysis algorithms, extending the QuAK framework.
Comprehensive Flattening Suite: Implementation of flattening procedures for all combinations of parent and child aggregators where emptiness and universality are known to be decidable. This covers parent functions $\{Sup, Inf, LimSup, LimInf, LimSupAvg, LimInfAvg\}$ and child functions $\{Min, Max, SumB, Sum+, Sum-\}$ .
Modular Architecture: A pipeline that translates NQAs into QAs with silent weights, which are then processed by QuAK's existing decision procedures for emptiness, inclusion, and safety-liveness analysis.
Experimental Evaluation: The tool was evaluated on two benchmark families:
- Response Time: Parametric NQAs ( $A_{n,k}$ ) modeling request-grant protocols with bounded pending requests ( $n$ ) and response times ( $k$ ).
- Resource Consumption: Parametric NQAs ( $B_{n,k}$ ) modeling systems with dynamically started/terminated processes and resource access patterns.

Results

The experimental evaluation demonstrates QuAK's effectiveness and scalability across different NQA types:

Response Time Benchmarks:
- For $(Sup, Sum+)$ emptiness, the tool scales well, with runtime showing a near-quadratic dependence on the response-time bound $k$ and mild dependence on the number of pending requests $n$ .
- For $(LimSupAvg, Sum+)$ emptiness and $(Sup, SumB)$ universality, runtime grows more rapidly with both parameters. Universality is consistently more expensive due to the need for PSpace procedures to handle nondeterminism in the flattened automaton.
Resource Consumption Benchmarks:
- The $(Sup, Max)$ emptiness check exhibits rapid blowup in both parameters ( $n$ and $k$ ) due to the combinatorial explosion of resource subsets tracked by active children.
- The $(LimSupAvg, Max)$ case is substantially harder, as it requires preserving exact return values for all active children, leading to memory exhaustion at smaller parameter values compared to the supremum case.

The results confirm that while explicit flattening can incur large state spaces—particularly when many child instances are active simultaneously or child configurations are dense—the tool successfully handles decidable instances of complex quantitative properties.

Significance

The paper claims to bridge the gap between the theoretical decidability of NQAs and practical verification. By extending QuAK, the authors enable the automated verification of quantitative properties, such as average response time, that are expressible in NQAs but not in standard QAs. The work establishes a foundation for analyzing systems with dynamically spawned tasks and unbounded costs, providing a practical framework for protocol latency analysis, service-level response-time monitoring, and resource-consumption analysis. The authors note that while the current implementation relies on explicit state construction, future work may explore symbolic representations to mitigate state-space blowup.