Active Learning of Symbolic Mealy Automata
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_ | 1866915500927221760 |
|---|---|
| author | Irie, Kengo Waga, Masaki Suenaga, Kohei |
| author_facet | Irie, Kengo Waga, Masaki Suenaga, Kohei |
| contents | We propose $Λ^*_M$-an active learning algorithm that learns symbolic Mealy automata, which support infinite input alphabets and multiple output characters. Each of these two features has been addressed separately in prior work. Combining these two features poses a challenge in learning the outputs corresponding to potentially infinite sets of input characters at each state. To address this challenge, we introduce the notion of essential input characters, a finite set of input characters that is sufficient for learning the output function of a symbolic Mealy automaton. $Λ^*_M$ maintains an underapproximation of the essential input characters and refines this set during learning. We prove that $Λ^*_M$ terminates under certain assumptions. Moreover, we provide upper and lower bounds for the query complexity. Their similarity suggests the tightness of the bounds. We empirically demonstrate that $Λ^*_M$ is i) efficient regarding the number of queries on practical benchmarks and ii) scalable according to evaluations with randomly generated benchmarks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14694 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Active Learning of Symbolic Mealy Automata Irie, Kengo Waga, Masaki Suenaga, Kohei Formal Languages and Automata Theory We propose $Λ^*_M$-an active learning algorithm that learns symbolic Mealy automata, which support infinite input alphabets and multiple output characters. Each of these two features has been addressed separately in prior work. Combining these two features poses a challenge in learning the outputs corresponding to potentially infinite sets of input characters at each state. To address this challenge, we introduce the notion of essential input characters, a finite set of input characters that is sufficient for learning the output function of a symbolic Mealy automaton. $Λ^*_M$ maintains an underapproximation of the essential input characters and refines this set during learning. We prove that $Λ^*_M$ terminates under certain assumptions. Moreover, we provide upper and lower bounds for the query complexity. Their similarity suggests the tightness of the bounds. We empirically demonstrate that $Λ^*_M$ is i) efficient regarding the number of queries on practical benchmarks and ii) scalable according to evaluations with randomly generated benchmarks. |
| title | Active Learning of Symbolic Mealy Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2509.14694 |