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

arXiv: https://arxiv.org/abs/2407.09775 · HTML: https://mlsanity.com/paper/2407.09775/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 13 Jul 2024.

## Builds on (most cited first, 6 of 6)

- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces](https://mlsanity.com/paper/1904.02931/) (2019)
- [Explaining Black Boxes on Sequential Data using Weighted Automata](https://mlsanity.com/paper/1810.05741/) (2018)
- [Active learning of timed automata with unobservable resets](https://mlsanity.com/paper/2007.01637/) (2020)
- [Inferring Symbolic Automata](https://mlsanity.com/paper/2112.14252/) (2021)
- [Active Learning of One-Clock Timed Automata using Constraint Solving](https://mlsanity.com/paper/2208.00412/) (2022)

## Abstract (arXiv)

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.