Automata Learning – Expect Delays
Gabriel Dengler, Sven Apel, Holger Hermanns · 2025
Read Automata Learning – Expect Delays by Gabriel Dengler, Sven Apel, Holger Hermanns (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-2508-16384.txt.
Introduction
Gabriel Dengler, Sven Apel, and Holger Hermanns study, in 2025, how to learn the behavior of machines whose transitions come with random delays. A learner can fold delay sampling into standard learning, but that wastes samples near the start states, collecting far more than needed there.
Their approach splits the job in two: first learn the logical behavior, then use that knowledge to aim delay sampling where it is actually needed. The split matters because two machines can behave identically yet differ in their delay patterns. On benchmarks the method beat the naive baseline widely, and a database join-order study showed it fits real settings too.
Catalog record
| CREATOR | Gabriel Dengler, Sven Apel, Holger Hermanns |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-16384
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Automata Learning – Expect Delays! Thanks: 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łodowska-Curie grant agreement 101008233 (MISSION). Affiliation: Saarland University, Saarland Informatics Campus, Saarbrücken, Germany Gabriel Dengler, Sven Apel, Holger Hermanns Abstract This paper studies AAL ( 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 ∗ 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. MM Mealy machine MDM Mealy delay machine AAL active automata learning SUL system under learning MAT Minimal Adequate Teacher OQ output query EQ equivalence query EO equivalence oracle CDF cumulative distribution function PDF probability density function I/O input/output RPP Rural Postman Problem CPP Chinese Postman Problem MDP Markov decision processes MM Mealy machine MDM Mealy delay machine w.l.o.g. without loss of generality MLE maximum likelihood estimation DKW Dvoretzky–Kiefer–Wolfowitz CTMC continous-time Markov chain RV random variable 1 Introduction The goal of AAL is to infer the behavioral structure of a SUL ( SUL ) by executing actions upon the SUL and observing its resulting behavior [ 70 , 69 ] . This technique is the basis for inferring formal models of possibly large and complex systems for the sake of further analysis [ 62 , 52 , 81 , 66 ] . Besides the logical behavior of a system, an important aspect in real-word systems is their real-time behavior, which often comes with stochastic imprecisions due to communication delays or internal computation steps consuming time. Learning the timing behavior can become very relevant, for instance to detect bottlenecks in the implementation or to adjust to observed system performance. 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 steps of the system and how these could be accounted for. These delay characteristics usually need to be considered as being stochastic in nature and are representable as manifestations of continuous-time probability distributions. There is a plethora of basic model families that come to mind as target models [ 31 ] for AAL in such a setting, including timed automata [ 1 , 21 ] , probabilistic automata [ 64 , 71 ] including Markov decision processes, Markov automata [ 22 , 27 ] , and stochastic (timed) automata [ 20 , 10 ] . Indeed, inspiring research work on AAL has been undertaken in many facets for timed automata [ 82 , 2 , 3 , 4 , 33 , 15 , 80 , 40 , 43 , 75 , 13 ] as well as MDP [ 55 , 73 , 72 , 6 , 8 ] . However, to the best of our knowledge, automata models that provide explicit support for stochastic delays have not been put into the AAL research focus. At the same time, these appear as natural candidates in scenarios where the delays of activities follow continuous probability distributions over time. These can be represented directly within stochastic (timed) automata or approximated as precisely as needed within Markov automata via phase-type fitting [ 7 ] . This paper aims at exploring this topic from ground up. For this purpose, we start with the goal of performing black-box learning of a deterministic MM ( MM ) while collecting the time needed to traverse transitions alongside learning. While we assume determinism for the state space, the timing behavior is assumed to follow continuous probability distributions. This makes it necessary to traverse each transition multiple times to obtain statistically sound estimations. We will 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. Furthermore, we consider it natural (albeit challenging) that the teacher has full knowledge of the time-abstract behavior, but that the time dependencies are entirely outside their knowledge, and thus the ground truth needs to (and can only) be inferred approximately through observations. Related work. For models that exhibit probabilistic decisions associated to actions, e.g., MDP or probabilistic MM , 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 ] . Thereby, the learner needs to reset the system frequently, which leads to considerable oversampling near the root, whereas other parts of the system are covered to a much lesser extent. 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 ] . In a timed setting, delays induced by transitions are often modeled using clocks or timers in automata or MM : This can be explicitly achieved by splitting transitions into two consecutive transitions [ 57 , 40 ] , where time is spent in the intermediate state, i.e., by waiting for the expiration of a delay timer. While these models are (distributions aside) more general than the MM structure considered in this paper, their use in AAL research comes with other side constraints that hamper application in the real-world settings we focus on: They predominantly consider deterministic behavior for each clock/timer and sometimes assume the existence of a smart teacher [ 82 , 75 ] that can explicitly answer more complex queries or provide hints to the learner. We do not assume the existence of any of these helpful features. In the literature, there are also some suggestions to learn stochastic timed models passively [ 50 , 51 , 65 ] , then resorting to state merging as in Alergia [ 16