Active Learning of Symbolic Automata over Rational Numbers

Automata learning has many applications in artificial intelligence and software engineering. Central to these applications is the L * algorithm, introduced by Angluin [3] . The L * algorithm learns deterministic finite-state automata (DFAs) in polynomial time when provided with a minimally adequate teacher. Unfortunately, the L * algorithm can only learn DFAs over finite alphabets, which limits its applicability. In this paper, we extend L * to learn symbolic automata whose transitions use predicates over rational numbers, i.e., over infinite and dense alphabets. Our result makes the L * algorithm applicable to new settings like (real) RGX, and time series. Furthermore, our proposed algorithm is optimal in the sense that it asks a number of queries to the teacher that is at most linear with respect to the number of transitions, and to the representation size of the predicates.