# Active Learning of Symbolic Automata Over Rational Numbers

arXiv: https://arxiv.org/abs/2511.12315 · HTML: https://mlsanity.com/paper/2511.12315/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 15 Nov 2025.

## Builds on (most cited first, 6 of 6)

- [Interpretable Sequence Classification via Discrete Optimization](https://mlsanity.com/paper/2010.02819/) (2020)
- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Learning Interpretable Temporal Properties from Positive Examples Only](https://mlsanity.com/paper/2209.02650/) (2022)
- [Reinforcement Learning with Stochastic Reward Machines](https://mlsanity.com/paper/2510.14837/) (2025)
- [Learning Regular Languages over Large Ordered Alphabets](https://mlsanity.com/paper/1506.00482/) (2015)
- [Learning Automata-Based Complex Event Patterns in Answer Set Programming](https://mlsanity.com/paper/2208.14820/) (2022)

## Abstract (arXiv)

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.