Learning Alternating Real-Time Automata

2026/06/18 by Kazuki Kinoshita, Masaki Waga · 1 voice
Computer Science · #cs.FL

paper · pdf

Abstract

We present the AL*RTA algorithm for learning alternating real-time automata (ARTAs) using membership and equivalence queries. AL*RTA combines ideas from AL*for learning alternating finite automata and NL*RTA for learning nondeterministic real-time automata. We first define ARTAs and show that alternation improves succinctness, although it does not increase expressive power. We then present AL*RTA and show its termination. Our empirical evaluation suggests that AL*RTA generally learns smaller automata than NL*RTA at the cost of more queries.

Citations

• Active Learning of Mealy Machines with Timers
• Active Learning of Deterministic Timed Automata with Myhill-Nerode Style Characterization
• Learning One-Clock Timed Automata
• A theory of timed automata
• Learning regular sets from queries and counterexamples
• Alternation

Discussions

• Kazuki Kinoshita, Masaki Waga: Learning Alternating Real-Time Automata https://arxiv.org/abs/2606.19822 https://arxiv.org/pdf/2606.19822 https://arxiv.org/html/2606.19822 [bsky, 0 points, 0 comments]

Related

• Automata Learning from Preference and Equivalence Queries
• Active Learning of Deterministic Timed Automata with Myhill-Nerode Style Characterization
• Alternating Nonzero Automata
• Learning real-time one-counter automata using polynomially many queries
• Learning Deterministic One-Counter Automata in Polynomial Time