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. 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.