A Myhill-Nerode Characterization and Active Learning for One-Clock Timed Automata
Abstract
We present a Myhill-Nerode style characterization for languages recognized by one-clock deterministic timed automata ( $$1$$ -DTA). Although there is only one clock, distinct automata may reset it differently along the same word. This adds a significant challenge in the search for a canonical automaton. Our characterization is based on a new perspective of $$1$$ -DTAs in terms of “half-integral” words that they accept, along with the reset information encoded by them We apply our results to develop $$\mathsf {L^*}$$ style algorithms that learn the canonical $$1$$ -DTA.
Fields of Study & Subjects
Machine Learning and Algorithms
Optimization and Search Problems
Formal Methods in Verification
Publication details
- Journal / source
- Lecture notes in computer science
- Publisher
- Springer Nature Switzerland
- Pages
- 419–437
- Publication date
- 1 January 2026
- Language
- EN