Active Learning of Symbolic Automata over Rational Numbers

Abstract

Automata learning has many applications in artificial intelligence and software engineering. Central to these applications is the L* algorithm, introduced by Angluin (1987). 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 for learning each predicate is optimal in the sense that it asks a number of queries to the teacher that is at most linear with respect to the size of their representation.