Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913430236037120 |
|---|---|
| author | Okudono, Takamasa Waga, Masaki Sekiyama, Taro Hasuo, Ichiro |
| author_facet | Okudono, Takamasa Waga, Masaki Sekiyama, Taro Hasuo, Ichiro |
| contents | Active learning of finite automata has been vigorously pursued for the purposes of analysis and explanation of black-box systems. In this paper, we study an L*-style learning algorithm for weighted automata over the max-plus semiring. The max-plus setting exposes a "consistency" issue in the previously studied semiring-generic extension of L*: we show that it can fail to maintain consistency of tables, and can thus make equivalence queries on obviously wrong hypothesis automata. We present a theoretical fix by a mathematically clean notion of column-closedness. We also present a nontrivial and reasonably broad class of weighted languages over the max-plus semiring in which our algorithm terminates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09775 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination Okudono, Takamasa Waga, Masaki Sekiyama, Taro Hasuo, Ichiro Formal Languages and Automata Theory Machine Learning Active learning of finite automata has been vigorously pursued for the purposes of analysis and explanation of black-box systems. In this paper, we study an L*-style learning algorithm for weighted automata over the max-plus semiring. The max-plus setting exposes a "consistency" issue in the previously studied semiring-generic extension of L*: we show that it can fail to maintain consistency of tables, and can thus make equivalence queries on obviously wrong hypothesis automata. We present a theoretical fix by a mathematically clean notion of column-closedness. We also present a nontrivial and reasonably broad class of weighted languages over the max-plus semiring in which our algorithm terminates. |
| title | Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination |
| topic | Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2407.09775 |