Automata Learning -- Expect Delays!
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908499224559616 |
|---|---|
| author | Dengler, Gabriel Apel, Sven Hermanns, Holger |
| author_facet | Dengler, Gabriel Apel, Sven Hermanns, Holger |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16384 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Automata Learning -- Expect Delays! Dengler, Gabriel Apel, Sven Hermanns, Holger Formal Languages and Automata Theory Software Engineering 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. |
| title | Automata Learning -- Expect Delays! |
| topic | Formal Languages and Automata Theory Software Engineering |
| url | https://arxiv.org/abs/2508.16384 |