Learning Alternating Real-Time Automata
For researchers in automata learning, this work offers a new algorithm that trades query efficiency for model compactness.
The paper introduces AL*RTA, an algorithm for learning alternating real-time automata, which produces smaller automata than nondeterministic counterparts but requires more queries.
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.