Minimization of Limit-Average Automata

Minimization of Limit-Average Automata

Jakub Michaliszyn, Jan Otop

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 2819-2825. https://doi.org/10.24963/ijcai.2021/388

LimAvg-automata are weighted automata over infinite words that aggregate weights along runs with the limit-average value function. In this paper, we study the minimization problem for (deterministic) LimAvg-automata. Our main contribution is an equivalence relation on words characterizing LimAvg-automata, i.e., the equivalence classes of this relation correspond to states of an equivalent LimAvg-automaton. In contrast to relations characterizing DFA, our relation depends not only on the function defined by the target automaton, but also on its structure. We show two applications of this relation. First, we present a minimization algorithm for LimAvg-automata, which returns a minimal LimAvg-automaton among those equivalent and structurally similar to the input one. Second, we present an extension of Angluin's L^*-algorithm with syntactic queries, which learns in polynomial time a LimAvg-automaton equivalent to the target one.
Keywords:
Machine Learning: Active Learning
Agent-based and Multi-agent Systems: Formal Verification, Validation and Synthesis
Multidisciplinary Topics and Applications: Validation and Verification