Active Learning of Symbolic Automata over Rational Numbers
Sebastian Hagedorn Gaete, Martín Muñoz, Cristian Riveros, Rodrigo Toro Icarte
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.
BibTeX
@inproceedings{aaai2026_activelearningof,
title = {Active Learning of Symbolic Automata over Rational Numbers},
author = {Sebastian Hagedorn Gaete and Martín Muñoz and Cristian Riveros and Rodrigo Toro Icarte},
booktitle = {AAAI 2026},
year = {2026}
}