Active Learning of Symbolic Automata Over Rational Numbers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912712115617792 |
|---|---|
| author | Hagedorn, Sebastian Muñoz, Martín Riveros, Cristian Icarte, Rodrigo Toro |
| author_facet | Hagedorn, Sebastian Muñoz, Martín Riveros, Cristian Icarte, Rodrigo Toro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12315 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Active Learning of Symbolic Automata Over Rational Numbers Hagedorn, Sebastian Muñoz, Martín Riveros, Cristian Icarte, Rodrigo Toro Machine Learning Formal Languages and Automata Theory 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. |
| title | Active Learning of Symbolic Automata Over Rational Numbers |
| topic | Machine Learning Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2511.12315 |