Active Learning of Deterministic Timed Automata with Myhill-Nerode Style Characterization
Lists
Only you see this
Abstract
We present an algorithm to learn a deterministic timed automaton (DTA) via membership and equivalence queries. Our algorithm is an extension of the L* algorithm with a Myhill-Nerode style characterization of recognizable timed languages, which is the class of timed languages recognizable by DTAs. We first characterize the recognizable timed languages with a Nerode-style congruence. Using it, we give an algorithm with a smart teacher answering symbolic membership queries in addition to membership and equivalence queries. With a symbolic membership query, one can ask the membership of a certain set of timed words at one time. We prove that for any recognizable timed language, our learning algorithm returns a DTA recognizing it. We show how to answer a symbolic membership query with finitely many membership queries. We also show that our learning algorithm requires a polynomial number of queries with a smart teacher and an exponential number of queries with a normal teacher. We applied our algorithm to various benchmarks and confirmed its effectiveness with a normal teacher.
BibTeX
@inproceedings{waga2023active,
author = {Masaki Waga},
title = {{Active Learning of Deterministic Timed Automata with Myhill-Nerode Style Characterization}},
booktitle = {CAV},
year = {2023},
doi = {10.1007/978-3-031-37706-8\_1},
}| Active Learning of Mealy Machines with Timers | arXiv · 2024 |
| Active Learning of Symbolic Automata over Rational Numbers | arXiv · 2025 |
| Learning deterministic probabilistic automata from a model checking perspective | Machine Learning · 2016 |
| Active Learning of Symbolic Mealy Automata | arXiv · 2025 |
| Learning Timed Automata via Genetic Programming | arXiv · 2018 |
| Automata with Timers | arXiv · 2023 |