A Myhill-Nerode Characterization and Active Learning for One-Clock Timed Automata

2026/01/21 by Kyveli Doveri, Pierre Ganty, B. Srivathsan · 1 voice
Computer Science · #cs.FL #cs.LO

paper · pdf · doi:10.48550/arxiv.2601.15104

arxiv published 2026/01/21 · arxiv updated 2026/04/14

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 L* style algorithms that learn the canonical 1-DTA.

Citations

• A Myhill-Nerode style Characterization for Timed Automata With Integer Resets
• Active Learning of Mealy Machines with Timers
• Active Learning of Deterministic Timed Automata with Myhill-Nerode Style Characterization
• Active Learning of One-Clock Timed Automata using Constraint Solving
• Learning One-Clock Timed Automata
• A theory of timed automata
• Learning regular sets from queries and counterexamples

Discussions

• Kyveli Doveri, Pierre Ganty, B. Srivathsan: A Myhill-Nerode Characterization and Active Learning for One-Clock Timed Automata https://arxiv.org/abs/2601.15104 https://arxiv.org/pdf/2601.15104 https:// [bsky, 0 points, 0 comments]

Related

• A Myhill-Nerode style Characterization for Timed Automata With Integer Resets
• Active Learning of Deterministic Timed Automata with Myhill-Nerode Style Characterization
• Learning One-Clock Timed Automata
• Active Learning of One-Clock Timed Automata using Constraint Solving
• Büchi-Kamp Theorems for 1-clock ATA