🤖 machine learning

SMT-Based Active Learning of Weighted Automata

This paper presents a parametric, SMT-based active learning algorithm for nondeterministic weighted automata that guarantees minimal results, ensures termination for finite semirings, and demonstrates superior efficiency and compactness compared to existing methods in extensive experiments.

Original authors: Tiago Ferreira, Kevin Batz, Alexandra Silva

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tiago Ferreira, Kevin Batz, Alexandra Silva

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 trying to teach a robot how to navigate a maze, but you don't know the maze's layout. You can ask the robot two types of questions:

"What happens if I take this path?" (The robot tells you the result, like "I get stuck" or "I find a treasure worth 5 gold coins.")
"Is this map you drew correct?" (The robot checks your map against the real maze and says "Yes" or "No, you missed a turn here.")

This is the core idea of Active Learning: an algorithm that learns a model by asking smart questions to a "Teacher" (the real system).

For a long time, these learning algorithms worked great for simple "Yes/No" mazes (like: Is this door open or closed?). But real-world systems are often more complex. They involve weights: costs, probabilities, or time. For example, "What is the cheapest way to get to the exit?" or "What is the probability of crashing?"

This paper introduces a new, powerful way to teach computers to learn these Weighted Automata (mazes with numbers attached to paths).

The Old Way: The "Table" Method

Previously, researchers used a method based on giant tables (called Hankel matrices). Imagine trying to solve a puzzle by filling out a massive spreadsheet where every cell depends on complex algebra rules.

The Problem: This spreadsheet method gets very messy and hard to solve when the numbers aren't just simple integers. It often fails to find the simplest possible map, or it gets stuck trying to prove it can finish the job. It's like trying to solve a Rubik's cube by writing down every possible move on a piece of paper; it works for small cubes but becomes impossible for big ones.

The New Way: The "SMT" Method

The authors propose a different approach: Constraint Solving. Instead of filling out a spreadsheet, they turn the learning problem into a giant logic puzzle.

The Analogy: The Detective and the SMT Solver
Imagine you are a detective trying to reconstruct a crime scene (the maze) based on witness statements (the Teacher's answers).

The Hypothesis: You guess a suspect and a timeline (a small map with a few states).
The Constraints: You write down a list of rules: "If the suspect was at the bank, they must have left by 5 PM," or "The total money stolen must equal $100."
The SMT Solver: This is a super-smart computer program (like a logic engine) that checks if your rules make sense. It asks, "Is there any way to arrange the suspect's movements so that all these rules are true?"
- If Yes: The solver gives you a valid map.
- If No: It tells you your map is impossible.

The paper's algorithm works like this:

It starts with a tiny, simple map.
It asks the Teacher for answers to specific paths.
It feeds these answers into the SMT Solver as a set of math rules.
The Solver tries to find a map that fits all the rules.
If the Teacher says, "No, that map is wrong because it fails on this specific path," the algorithm adds that path to the rules and asks the Solver to try again.

Why is this better?

The paper claims three main advantages, explained simply:

1. It Always Finds the Smallest Map (Minimality)
The old methods sometimes gave you a map with 10 rooms when a 3-room map would have worked. The new SMT method is designed to find the smallest possible map that fits the rules. It's like finding the most efficient route rather than just a route.

2. It Works with "Weird" Math
The old methods struggled with complex number systems (like "Tropical" math, where you add numbers but take the minimum, or "Bottleneck" math). The new method can handle these "weird" math systems by translating them into logic puzzles that the computer solver understands. It's like having a universal translator that can turn complex math into simple "True/False" questions.

3. It's Faster and Needs Fewer Questions
In their experiments, the new method learned complex maps much faster than the old "table" method. It also needed to ask the Teacher fewer questions to get the right answer.

The "Naive" Baseline: They compared their method to a "dumb" version that just guesses randomly. The new method was vastly superior.
The "State-of-the-Art" Competitor: They compared it to the best existing method. The new method produced maps that were significantly smaller (sometimes 10x smaller!) and still finished in a reasonable amount of time.

The "Magic" Ingredient: SMT Solvers

The secret sauce is SMT Solving (Satisfiability Modulo Theories). Think of an SMT solver as a super-powered logic checker. It doesn't just check if a sentence is true; it checks if a complex set of mathematical rules can be true at the same time.

The authors proved that for many types of math systems (including finite ones and some infinite ones), this logic puzzle is solvable.
They showed that if the math system is finite (like a limited set of numbers), the algorithm is guaranteed to finish.

Summary

The paper presents a new way to teach computers to understand complex, weighted systems. Instead of using old, clunky spreadsheet methods, they turned the problem into a logic puzzle that a modern computer solver can crack.

Result: It finds the simplest possible model.
Result: It works on a wider variety of math systems than before.
Result: It is faster and asks fewer questions than previous methods.

The authors tested this on thousands of examples and found it to be a robust, practical tool for learning these complex systems, offering a strong alternative to the methods used for the last decade.

Technical Summary: SMT-Based Active Learning of Weighted Automata

Problem Statement

Active automata learning, pioneered by Angluin's $L^\star$ algorithm, has become a standard technique for inferring models of unknown components in formal verification. While $L^\star$ -style methods are well-established for Boolean automata (deterministic and nondeterministic), extending them to Weighted Finite Automata (WFAs) has proven significantly more challenging. WFAs generalize Boolean automata by assigning weights from a semiring to transitions, enabling the modeling of quantitative properties such as cost, probability, and resource consumption.

Existing approaches to learning WFAs rely on generalizations of the Hankel matrix or observation table (e.g., $WL^\star$ ). These methods require reasoning about the algebraic structure of the underlying semiring. Consequently, proving termination and minimality is subtle and often restricted to specific algebraic classes (e.g., fields, principal ideal domains). For many practically relevant semirings, such as the Tropical semiring or the Bottleneck semiring, termination guarantees are either unknown or do not ensure minimal automata. Furthermore, existing algorithms often produce non-minimal models or fail to scale effectively over infinite semirings.

Methodology

The authors propose a novel, constraint-based active learning algorithm that casts the learning problem directly as a satisfiability problem solvable by SMT (Satisfiability Modulo Theories) solvers.

Core Approach

Instead of refining an observation table, the algorithm incrementally constructs a system of equations over the given semiring $S$ . The solutions to this system correspond exactly to nondeterministic WFAs that agree with the "teacher" (the target language) on all observed queries.

The learning process follows a standard active learning loop (Algorithm 1):

Hypothesis Generation: The algorithm attempts to find an $n$ -state WFA that is consistent with the current observation set $O$ . This is delegated to a subroutine getAutomaton.
Equivalence Query: If a consistent hypothesis $H$ is found, the teacher is queried to verify if $H$ recognizes the target language $L$ .
Counterexample Handling: If the teacher provides a counterexample $w$ (where $H(w) \neq L(w)$ ), $w$ is added to $O$ , and the loop repeats with the strengthened constraints.

The `getAutomaton` Subroutine

The paper presents two implementations for getAutomaton:

Naive Baseline: Directly encodes the semantics of the WFA. It treats initial weights, transition matrices, and final weights as unknown variables and solves the equation $out(w) = \text{semantics}(w)$ for all $w \in O$ .
Optimized (SWAL): Utilizes a coalgebraic perspective and the concept of state languages. Instead of solving for the global language directly, it introduces intermediate variables representing the language accepted from each state. This results in a system of equations where:
- Stabilization constraints ensure that state languages are consistent with transition weights.
- Spanning constraints ensure the initial weights correctly combine state languages to match the target output.
- Key Insight: While this encoding introduces more variables and equations, it exposes shared substructures (suffixes) between observations. This allows SMT solvers to reuse intermediate results, significantly improving scalability compared to the naive approach.

Decidability and Semirings

The algorithm is parametric in the semiring. The authors identify that for decidable semirings (where the satisfiability of finite equation systems is decidable), the getAutomaton subroutine can be implemented soundly and completely.

Finite Semirings: Trivially decidable via brute-force or SMT.
Infinite Semirings: The paper provides encodings for the Tropical semiring ( $\min, +$ ), Bounded Tropical semirings, and the Bottleneck semiring ( $\max, \min$ ) into decidable theories like Quantifier-Free Linear Integer Arithmetic (QF-LIA) and Quantifier-Free Bit-Vectors (QF-BV).

Key Contributions

Novel Algorithm: A new SMT-based active learning algorithm for nondeterministic WFAs that is parametric in the semiring.
Minimality Guarantee: Unlike $L^\star$ -style methods which often lack minimality guarantees outside specific algebraic structures, this algorithm is guaranteed to produce minimal WFAs upon termination, regardless of the semiring.
Termination Conditions: The authors prove partial correctness and provide sufficient conditions for termination. Specifically, they prove that the algorithm terminates for all finite semirings. For infinite semirings, while termination is not theoretically guaranteed by the same cardinality arguments, the implementation demonstrates practical success.
Constraint-Based Synthesis: The paper introduces the first constraint-based generation algorithm for WFAs, enabling SMT-based synthesis. It identifies specific semirings where the resulting constraint systems are decidable.
Experimental Evaluation: A comprehensive evaluation comparing the proposed method (SWAL) against a naive baseline and the state-of-the-art $WL^\star$ algorithm.

Experimental Results

The authors implemented the algorithm (SWAL) in OCaml using the Z3 solver and evaluated it on over 5,000 randomly generated benchmarks across Boolean, Tropical, Bounded Tropical, and Bottleneck semirings.

vs. Naive Baseline: SWAL significantly outperforms the naive encoding in both runtime and scalability. While the naive approach struggles to learn automata with more than 2–6 states (depending on the semiring), SWAL successfully learns minimal automata with up to 8 states. The optimized encoding (state languages) reduces the number of timeouts/out-of-memory errors by orders of magnitude.
vs. $WL^\star$ : When compared to $WL^\star$ $W L^{⋆}$ (a state-of-the-art algorithm for principal ideal domains):
- Minimality: SWAL consistently produces minimal automata, whereas $WL^\star$ often produces automata up to 10 times larger.
- Efficiency: SWAL requires fewer output queries (interactions with the teacher) than $WL^\star$ .
- Runtime: SWAL is competitive in runtime, often terminating faster and with fewer resource failures (TO/OOM) than $WL^\star$ .
Incrementality: Enabling incremental SMT solving drastically reduces learning time and resource usage, confirming the suitability of the constraint-based approach for incremental learning.

Significance and Claims

The paper positions constraint-based learning as a practical and robust alternative to traditional Hankel/ $L^\star$ -style methods for weighted automata, particularly in verification-oriented settings.

Robustness: The approach handles a broader range of semirings (including infinite ones like Tropical) where algebraic termination proofs for $L^\star$ -style methods are difficult or non-existent.
Minimality: The guarantee of minimality is a crucial advantage, as minimal models are essential for efficient verification and abstraction.
Scalability: The experimental results demonstrate that SMT-based synthesis can scale to learn complex, minimal weighted automata that are currently out of reach for existing algorithms.

The authors conclude that while they do not provide a general termination proof for all infinite semirings (a known open problem), their method offers a practical solution that successfully learns minimal WFAs in scenarios where previous methods fail or produce suboptimal models. Future work includes exploring more incremental hypothesis updates and extending the approach to probabilistic automata.