Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
<|reference_start|>Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination: 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.<|reference_end|>
@article{okudono2024learning,
    title={Learning Weighted Finite Automata over the Max-Plus Semiring and its
  Termination},
    author={Takamasa Okudono, Masaki Waga, Taro Sekiyama, and Ichiro Hasuo},
    journal={arXiv preprint arXiv:2407.09775},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.09775},
    primaryClass={cs.FL cs.LG}
}