Automata Learning -- Expect Delays!

arXiv:2508.16384 · cs.FL, cs.SE · Submitted 2025-08-22 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Automata Learning -- Expect Delays!".

Title and authors: Tom: Let's talk about what this paper is actually proposing in "Automata Learning -- Expect Delays!". They are suggesting a way to separate the learning of the machine's logical behavior from the act of sampling those actual transition delays.

Jane: So, instead of just throwing delay samples into every step, they want the learner to first figure out what the machine does logically before figuring out how often it needs to sample those delays.

Lu: That separation is smart because it means you get information from learning the logical behavior that you can then use to build an efficient sequence for collecting those delay samples.

Meng: I’m thinking about this in terms of cost; if the learner knows what transitions are important, they can focus their sampling budget where it actually yields useful data, instead of just hitting every transition a fixed number of times.

Lalam: So, the core idea is using the knowledge gained from learning the logical structure to guide you toward an efficient input sequence for gathering delay samples.

Tom: Exactly. It turns what was a naive integration into something that uses learned behavior to guide the sampling process, which addresses that oversampling issue they mentioned earlier.

Jane: It seems like they're trying to get a better balance between learning the system and getting reliable delay measurements for stochastic delays.

The paper's summary: Tom: The paper introduces something called Mealy delay machines, or MDMs, which are basically standard Mealy machines but with a description of how the transition delays behave using continuous probability distributions.

Jane: So they model the delay not as a single fixed number, but as a whole range of possibilities described by some kind of distribution.

Lu: The semantic interpretation they set up is that any sequence of inputs will create a probability space on timed output words defined by something called a cylinder set construction.

Meng: That sounds mathematically heavy; what does that actually mean for the engineer trying to debug or deploy this kind of system?

Lalam: It means they are treating the delay behavior as continuous, which allows them to model it using standard tools from continuous-time probability distributions.

Tom: The main technical challenge they tackle is finding approximations for these probability distributions of the transition delays by visiting each transition at least k times in N steps.

Jane: So, if you have a distribution for the delay, you need to sample that distribution enough times to get a good estimate of what it looks like.

Lu: They frame this as needing to visit every transition at least k in N times just to approximate the CDFs of those transitions according to the delay distribution D.

The paper's improvements: Tom: One major improvement they propose is separating behavior learning from delay sampling, which we already touched on, but they also look at handling more complex structures.

Jane: They consider scenarios where a machine's logical structure is more complex than the minimal machine they first learn.

Lu: To handle that, they construct an expanded model called the expanded Mealy machine Md based on the learned minimal model M prime by imposing constraints like stutter-free and d step confluence.

Meng: I'm wondering what that actually means for complexity; if you add these constraints to build Md, how does it affect the size of this new machine compared to the original one?

Tom: The paper claims this construction results in a size for Md that is linear with the size of the state space S prime and exponential only in the selection of d.

Jane: So, even with these complex constraints, they manage to keep that growth under control, depending on how deep you go into those specific rules.

Lalam: That’s a big win if it means you don't end up with an exponential explosion in the model size just because you're trying to capture finer delay differences.

Conclusion: Tom: So, to wrap up on "Automata Learning -- Expect Delays!", they showed that by using this expanded model Md, their sampling-based L star method outperforms the naive baseline by a large margin in the empirical evaluations.

Jane: It sounds like the main result is that separating learning from sampling and using this structure helps you get better results without drowning in unnecessary samples.

Lu: The runtime for both methods scales linearly with k once the initial phase of L star learning finishes, which is pretty good for scalability if k isn't too huge.

Meng: But they also noted that increasing that parameter d actually increases the runtime, which means you have to be careful when tuning those structural constraints.

Lalam: It seems like they’ve established a solid framework for active learning in systems with stochastic delays, giving us a formal way to approach this problem.

Tom: Their conclusion is that combining learning just the I/O structure with an efficient way to subsequently collect samples of transition delays provides a better path than the straightforward adaptation of standard active learning algorithms.

Jane: It’s encouraging because it gives us a clear method for dealing with these tricky stochastic elements in automata models.

Lu: Future work they hint at involves exploiting the cost model underlying the rural postman problem to distinguish between resets and actual transition traversals based on what those resets truly induce.

Meng: That sounds like practical stuff; knowing the true overhead of a reset versus just traversing an edge is crucial for deciding if you should bother sampling it or not.

Lalam: Exactly, that moves it from just theoretical modeling to making decisions about actual system behavior under real constraints.

Gabriel Dengler, Sven Apel, Holger Hermanns

Saarland University

cs.FL, cs.SE

Submitted: 2025-08-22

Updated: 2025-08-22

Comments: Accepted at Integrated Formal Methods (iFM) 2025

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: Automata Learning – Expect Delays! This paper studies active automata learning (AAL) in the presence of stochastic delays and proposes a method to efficiently collect necessary delay samples by…

Key concepts

Mealy Delay Machines (MDMs)
These are extended Mealy machines that include a continuous probability distribution describing the stochastic delay for every transition. They model how the output word's timing is probabilistic based on the input sequence, allowing researchers to analyze timed behavior.
Separating Learning and Sampling
The authors propose learning only the minimal logical behavior first using standard AAL methods. Then, they construct a separate sequence of inputs specifically designed to sample the transition delays efficiently, rather than sampling randomly across all possible states.
Directed Rural Postman Problem (RPP)
After separating learning and sampling, the problem of finding the minimum cost input sequence is reduced to an RPP with multiple edges. This mathematical structure helps in finding a path that covers every required transition at least k times with minimal total cost.
Expanded MM Md
For complex models, they construct an expanded machine based on the learned minimal model using injective bisimilarity. This technique ensures that states with the same logical behavior but different delay characteristics are distinguishable, keeping the model size manageable.

Terminology

Summary

Automata Learning – Expect Delays! p. 0

Where the paper says it

Automata Learning – Expect Delays! ⋆ Gabriel Dengler , Sven Apel , and Holger Hermanns Saarland University, Saarland Informatics Campus, Saarbr¨ucken, Germany Abstract.

This paper studies active automata learning (AAL) in the presence of stochastic delays and proposes a method to efficiently collect necessary delay samples by separating behavior learning from delay sampling The authors address the problem of oversampling near the root of the state space when integrating delay sampling into AAL algorithms like L∗ by using information gained from learning logical behavior to guide efficient input sequences for collecting delay samples. p. 0
Where the paper says it

While it is possible to na¨ıvely integrate the delay sampling into AAL algorithms such as L ∗ , this leads to considerable oversampling near the root of the state space. We address this problem by separating conceptually the learning of behavior and delays such that the learner uses the information gained while learning the logical behavior to arrive at efficient input sequences for collecting the needed delay samples.

Modeling Stochastic Delays

The paper introduces Mealy delay machines (MDMs) which extend standard Mealy machines by including a description of the stochastic delay behavior for each transition as a continuous probability distribution The semantic interpretation of an MDM is defined such that any given input word induces a probability space on timed output words given by a standard cylinder set construction. A transition delay is modeled as a CDF, denoted by D: S × I → F+0. p. 5

Where the paper says it

Definition 3. An MDM is a 7-tuple D = (S, I, O, s0, δ, λ, D), where the first 6 components constitute an MM (called the underlying MM) and D : S × I → F+ 0 represents the probabilistic delay behavior of each transition as CDF.

The core problem is to find approximands of the CDFs of transitions according to D by visiting each transition ⟨s, i⟩ ∈ S × I at least k in N times. p. 6
Where the paper says it

7 of D and find approximands of the CDFs of transitions according to D by visiting each transition ⟨s, i⟩ ∈ S × I at least k ∈ N times. This is the central problem we are aiming to solve.

Separating Learning and Sampling

The authors argue that it is theoretically justified and algorithmically beneficial to work with a global constant k of necessary transition traversals per transition to be considered. They propose separating the process of inferring the I/O behavior from that of sampling the delays, starting by learning the underlying minimal MM M′ using conventional AAL algorithms like L∗. p. 6

Where the paper says it

2 Efficient Coverage of Learned Mealy Machine To address this problem, we separate the process of inferring the I/O behavior from that of sampling the delays. We start by learning the underlying minimal MM M′ underlying D by some conventional AAL algorithms, e.

After this, they construct a sequence of input actions to cover every transition in D sufficiently often with minimum total cost. p. 7
Where the paper says it

After that, we can assume that each transition ⟨s, i⟩ ∈ S ×I of D has already been traversed some K(s, i) ∈ N0 times while inferring the minimal MM M′ , and we thus know that it needs no more than further K′ (s, i) = max(0, k − K(s, i)) visits. With this, we will construct a sequence of input actions to cover every transition in D sufficiently often, with minimum total cost.

This reduces the problem to the directed Rural Postman Problem (RPP) with multiple edges. p. 7
Where the paper says it

With this, we will construct a sequence of input actions to cover every transition in D sufficiently often, with minimum total cost. Concretely, the resulting problem can be reduced to the directed Rural Postman Problem (RPP) [26,61] with multiple edges, a variant of the Chinese Postman Problem (CPP) [24].

Handling Complex Structures

The paper investigates the case where an MDM D has a more complex structure than its underlying minimal MM M′ by imposing restrictions such as stutter-free and d-step confluence. They construct an expanded MM Md from the learned minimal MM M′ based on these assumptions, which is injective bisimilar to M. p. 7

Where the paper says it

In the general case, when the subgraph of G spanned by mandatory edges is not weakly connected, it can happen that G including the edges needed for 2 We do not know whether the RPP limited to the case-specific graphs G we construct is NP-complete, also considering the expansion of the minimal MM M′ in Sec. The constructed multigraph G is not fully general, because of the multiplicity of the edges and the structure itself being dependent on the previously learned graph and the expanded MM.

This construction results in a size of Md being linear in the size of the state space S′ and exponential only in the selection of d. p. 9
Where the paper says it

Otherwise, we can continue the general learning procedure of L ∗ as usual by adding any test word longer than d that arises by a counterexample (where, however, each newly added test word only needs to be queried once). Obviously, the size of the test set T now has an exponential size regarding the parameter d, and one could argue that it is better to gradually increase T through counterexamples.

Empirical Evaluation and Results

The empirical evaluation compares the baseline implementation based on L∗ with an improved method using the expanded MM Md. The results show that the sampling-based L∗ is outperformed by the approach using the expanded MM Md by a large margin. The runtime for both methods grows linearly with k once the effect of the initial L∗ step fades out. Furthermore, increasing parameter d results in an increased runtime, in line with the findings reported in Sec. p. 2

Where the paper says it

We then turn to the more intricate situation where certain sequences through the learned MM come with distinct delay characteristics albeit being indistinguishable from the perspective of the logical structure in isolation (Sec. Our theoretical findings are supported by a prototypical implementation, which we empirically evaluate on publicly available benchmark models (Sec.

6. The study also investigates applicability in a realistic setting by studying the join order in a relational database. p. 0
Where the paper says it

We put emphasis on treating cases in which identical input/output behaviors might stem from distinct delay characteristics. Finally, we provide empirical evidence that our method outperforms the na¨ıve baseline across a wide range of benchmarks and investigate its applicability in a realistic setting by studying the join order in a relational database.

Deriving Sample Size for Distributions

The paper details the derivation of the needed number of samples to derive the sample mean X of an exponentially distributed RV X with parameter λ and mean E[X] = µ. For a confidence of 1 − δ = 0.99, a maximum relative error of ε ≈ 0. p. 4

Where the paper says it

If we are instead interested in bounding the approximation error of the distribution’s mean, we can resort to Chebyshev’s inequality [29] (adapted to the sample mean) when assuming a maximum variance or Hoeffding’s inequality [34] when assuming a lower and upper bound to find an appropriate k for an absolute error bound. Furthermore, in the special case of exponential distributions, we can directly determine the number of samples k needed to achieve a relative error bound (see Appendix C).

081 is obtained when using k = 1000 samples for each edge. p. 8
Where the paper says it

Then, no Eulerian circuit can be found even if the number of incoming and outgoing edge multiplicities at each node were equal. In this case, our implementation resorts to the following: We compute the minimum spanning arborescence of minimum weight when using weight zero for edges that need to be covered and weight one elsewhere [18,25], resulting in a weakly-connected graph.

This analysis shows how the normal distribution approximation can be used to find the needed k. p. 4
Where the paper says it

If we are instead interested in bounding the approximation error of the distribution’s mean, we can resort to Chebyshev’s inequality [29] (adapted to the sample mean) when assuming a maximum variance or Hoeffding’s inequality [34] when assuming a lower and upper bound to find an appropriate k for an absolute error bound. Furthermore, in the special case of exponential distributions, we can directly determine the number of samples k needed to achieve a relative error bound (see Appendix C).

Complete Benchmarking Results

The appendix presents an exhaustive benchmarking of a publicly available test suite for MMs. Table 7 shows the results for collection of bank cards. p. 1

Where the paper says it

, MDPs or probabilistic MMs, it is—as in our scenario—essential that each input query will be asked multiple times to get statistically robust estimates of the SUL’s behavior. Concepts from the literature that adapt L ∗ for probabilistic models either introduce queries that return the sampled results as an observation tree [55] or equip the teacher with the ability to sample the SUL and thereby obtain estimations of the transition probabilities to be used by the learner [73].

Table 9 shows the benchmarking results for MQTT models (part 2). p. 1
Where the paper says it

, MDPs or probabilistic MMs, it is—as in our scenario—essential that each input query will be asked multiple times to get statistically robust estimates of the SUL’s behavior. Concepts from the literature that adapt L ∗ for probabilistic models either introduce queries that return the sampled results as an observation tree [55] or equip the teacher with the ability to sample the SUL and thereby obtain estimations of the transition probabilities to be used by the learner [73].

The final table, Table 12, presents benchmarking results for TLS (part 2). p. 0
Where the paper says it

One of the prominent past applications of AAL is related to finding critical bugs in protocol implementations [30]. Since these implementations first and foremost are meant to provide high performance communication services, it seems natural to consider information about the delay characteristics of the various steps as additional valuable information to discover fast and slow ⋆ This work was partially funded by DFG grant 389792660 as part of TRR 248 CPEC, the European Union (EU) under the INTERREG North Sea project STORM SAFE of the European Regional Development Fund, and the EU’s Horizon 2020 research and innovation programme under Marie Sk lodowska-Curie grant agreement 101008233 (MISSION).

These experiments demonstrate that increasing parameter d results in an increased runtime, in line with the findings reported in Sec. p. 1
Where the paper says it

Instead of actively learning the MDP, there is also the possibility to adapt passive learning approaches like Alergia [16] to a probabilistic setting [48]. However, experiments demonstrate an overall better performance for active learning approaches [73].

6. The size of the MM Md does not change anymore at d = 3, as it is 3-step confluent. p. 8
Where the paper says it

The second restriction requires that two states which are equivalent regarding the I/O behavior also show the same delay behavior at the latest after d steps: Definition 6. An MDM D = (S, I, O, s0, δ, λ, D) is d-step confluent iff for all states s1, s2 ∈ S with s1 ∼IO s2 and all words w ∈ I ≥d such that δ(s1, w) as well as δ(s2, w) do not include a self-loop, it holds δ(s1, w) = δ(s2, w).

Conclusion

The paper has studied the active learning of Mealy machines with stochastic transition delays. To outperform the straightforward adaptation of standard AAL algorithms, they proposed a combination of learning just the I/O structure with an efficient way to subsequently collect samples of transition delays. p. 0

Where the paper says it

While it is possible to na¨ıvely integrate the delay sampling into AAL algorithms such as L ∗ , this leads to considerable oversampling near the root of the state space. We address this problem by separating conceptually the learning of behavior and delays such that the learner uses the information gained while learning the logical behavior to arrive at efficient input sequences for collecting the needed delay samples.

The empirical results reported are very encouraging. p. 1
Where the paper says it

, MDPs or probabilistic MMs, it is—as in our scenario—essential that each input query will be asked multiple times to get statistically robust estimates of the SUL’s behavior. Concepts from the literature that adapt L ∗ for probabilistic models either introduce queries that return the sampled results as an observation tree [55] or equip the teacher with the ability to sample the SUL and thereby obtain estimations of the transition probabilities to be used by the learner [73].

Future work will exploit the cost model underlying the RPP to discriminate between resets and transition traversals based on the true overhead a reset induces.

Acknowledgments

The authors thank Tobias Dick from Saarland University for his assistance in conducting the database case study and the fruitful discussions.

Data availability statement

The artifact of this paper—a reproduction package for the experiments in Sec. 6 and Sec. 7—is available at DOI 10. p. 2

Where the paper says it

We then turn to the more intricate situation where certain sequences through the learned MM come with distinct delay characteristics albeit being indistinguishable from the perspective of the logical structure in isolation (Sec. Our theoretical findings are supported by a prototypical implementation, which we empirically evaluate on publicly available benchmark models (Sec.

6084/m9.figshare.29966641. The source code is available on https://dgit. p. 2
Where the paper says it

We then turn to the more intricate situation where certain sequences through the learned MM come with distinct delay characteristics albeit being indistinguishable from the perspective of the logical structure in isolation (Sec. Our theoretical findings are supported by a prototypical implementation, which we empirically evaluate on publicly available benchmark models (Sec.

cs.uni-saarland. p. 0
Where the paper says it

Automata Learning – Expect Delays! ⋆ Gabriel Dengler , Sven Apel , and Holger Hermanns Saarland University, Saarland Informatics Campus, Saarbr¨ucken, Germany Abstract.

de/gabriel. p. 0
Where the paper says it

Automata Learning – Expect Delays! ⋆ Gabriel Dengler , Sven Apel , and Holger Hermanns Saarland University, Saarland Informatics Campus, Saarbr¨ucken, Germany Abstract.

dengler/al-expect-delays. p. 0
Where the paper says it

Automata Learning – Expect Delays! ⋆ Gabriel Dengler , Sven Apel , and Holger Hermanns Saarland University, Saarland Informatics Campus, Saarbr¨ucken, Germany Abstract.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Active automata learning can be improved by separating behavior learning from delay sampling to avoid considerable oversampling near the root of the state space. This allows a learner to use information gained while learning logical behavior to arrive at efficient input sequences for collecting the needed delay samples.

  2. The system can be enhanced by reducing computational complexity in coverage strategies, as the problem is reduced to a directed Rural Postman Problem (RPP) which, when restricted to mandatory edges forming a weakly connected component, allows for an Eulerian circuit construction.

  3. For complex models where certain sequences through the learned MM come with distinct delay characteristics albeit being indistinguishable from the perspective of the logical structure in isolation, the system can be improved by constructing an expanded MM Md using injective bisimilarity to handle state separation without resorting to exponential growth in test suite size.

  4. The AI system can gain robustness by employing constraints on behavioral equivalence, such as stutter-free and d-step confluent, which ensures that states with the same logical behavior also exhibit distinguishable delay behaviors for a bounded depth d.

  5. The learning process can be further optimized by using an approach where the number of samples k is fixed as a constant across the entire structure, simplifying the problem statement to finding input sequences to cover every transition at least k times.

  6. For real-world applications like relational databases, the system can be used to discover unknown join orders by increasing parameter d, as seen in experimental results where increasing parameter d results in an increased runtime, in line with the findings reported in Sec. 6.

Abstract

This paper studies active automata learning (AAL) in the presence of stochastic delays. We consider Mealy machines that have stochastic delays associated with each transition and explore how the learner can efficiently arrive at faithful estimates of those machines, the precision of which crucially relies on repetitive sampling of transition delays. While it is possible to naïvely integrate the delay sampling into AAL algorithms such as L*, this leads to considerable oversampling near the root of the state space. We address this problem by separating conceptually the learning of behavior and delays such that the learner uses the information gained while learning the logical behavior to arrive at efficient input sequences for collecting the needed delay samples. We put emphasis on treating cases in which identical input/output behaviors might stem from distinct delay characteristics. Finally, we provide empirical evidence that our method outperforms the naïve baseline across a wide range of benchmarks and investigate its applicability in a realistic setting by studying the join order in a relational database.

Sources

Related papers