Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
This work addresses a specific issue in automata learning for black-box system analysis, but it is incremental as it builds on existing L*-style algorithms.
The paper tackled the problem of active learning for weighted automata over the max-plus semiring, where previous methods could fail due to consistency issues, and presented a theoretical fix with a mathematically clean notion of column-closedness, along with a nontrivial class of languages where the algorithm terminates.
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.