Minimization of Limit-Average Automata

Jakub Michaliszyn; Jan Otop

IJCAI 2021poster3 citations

Minimization of Limit-Average Automata

Abstract

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.

Machine Learning: Active LearningAgent-based and Multi-agent Systems: Formal Verification, Validation and SynthesisMultidisciplinary Topics and Applications: Validation and Verification

BibTeX

@inproceedings{ijcai2021p388,
  title     = {Minimization of Limit-Average Automata},
  author    = {Michaliszyn, Jakub and Otop, Jan},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Zhi-Hua Zhou},
  pages     = {2819--2825},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/388},
  url       = {https://doi.org/10.24963/ijcai.2021/388},
}