Minimization of Limit-Average Automata

Michaliszyn, Jakub; Otop, Jan

doi:10.24963/ijcai.2021/388

Minimization of Limit-Average Automata

Jakub Michaliszyn, Jan Otop

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2819-2825.

https://doi.org/10.24963/ijcai.2021/388

Keywords

Agent-based and Multi-agent Systems: Formal Verification, Validation and Synthesis
Machine Learning: Active Learning
Multidisciplinary Topics and Applications: Validation and Verification

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.

Jakub Michaliszyn, and Jan Otop. 2021. Minimization of Limit-Average Automata. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2819–2825. https://doi.org/10.24963/ijcai.2021/388

@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    = {Prof. 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},
}

TY  - CPAPER
TI  - Minimization of Limit-Average Automata
AU  - Michaliszyn, Jakub
AU  - Otop, Jan
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 2819
EP  - 2825
DO  - 10.24963/ijcai.2021/388
UR  - https://doi.org/10.24963/ijcai.2021/388
ER  -