{"ID":2841395,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.12315","arxiv_id":"2511.12315","title":"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. 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.","short_abstract":"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. Unfortunatel...","url_abs":"https://arxiv.org/abs/2511.12315","url_pdf":"https://arxiv.org/pdf/2511.12315v1","authors":"[\"Sebastian Hagedorn\",\"Martín Muñoz\",\"Cristian Riveros\",\"Rodrigo Toro Icarte\"]","published":"2025-11-15T18:04:36Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.FL\"]","methods":"[]","has_code":false}