Paper ID: 2407.09775

Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination

Takamasa Okudono, Masaki Waga, Taro Sekiyama, Ichiro Hasuo

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.

Submitted: Jul 13, 2024