Learning weighted automata over principal ideal domains (Q2200852)

The contribution considers the learning of weighted automata over principal ideal domains. The learning scenario is Angluin's minimally adequate teacher setup in which an oracle answers coefficient and equivalence queries. A coefficient query asks for the weight of a given input string in the weighted language to be learnt. An equivalence query presents the oracle with a weighted automaton and asks it whether this automaton represents the sought weighted language. Such a weighted automaton is essentially a finite-state automaton in which each transition additionally carries a weight from a particular weight structure. The weight structures considered are general semirings, but the main results are obtained for principal ideal domains. It is demonstrated that the observation-table approach and in particular the main notion of closedness of the table, both essentially due to Angluin, transfer faithfully to the mentioned setting, which yields that the corresponding learning problem is also efficiently solvable in principal ideal domains. The closedness condition is suitably adapted by the authors and they demonstrate that the algorithm terminates (due to the equivalence query the algorithm can only terminate with correctly learnt automata) iff a certain ascending chain condition is met, which is automatically true in all principal ideal domains. Additionally, the authors demonstrate that the algorithm (also called \(\mathrm L^\star\)) fails for more general weight structures as evidenced by the semiring of nonnegative integers which is not a principal ideal domain (albeit embeddable in one). The contribution is well written and understandable. Some knowledge about weighted automata and linear algebra is assumed on behalf of the reader, but the writing is otherwise perfectly comprehensible for anyone with some effort. Previous knowledge of similar variants of the algorithm is certainly helpful, but not strictly necessary. For the entire collection see [Zbl 1440.68008].