2024/07/13 by Takamasa Okudono, Okudono, Takamasa, Masaki Waga +5
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Search Problems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2407.09775
openalex publication_date 2024/07/13 · openalex created_date 2024/07/17 · openalex updated_date 2026/07/28
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.