一句话：为 min-plus、max-plus 与自然数半环上的五类加权自动机片段建立泵引理，并证明歧义层次严格。
本文研究半环上加权自动机所定义函数类的结构性质。作者针对 min-plus 半环、max-plus 半环以及自然数半环，为五类加权自动机片段分别建立了泵引理，给出函数在长输入上可被“泵送”或分解的条件。作为主要推论，论文证明了在 min-plus 与 max-plus 半环上，无歧义、有限歧义、多项式歧义加权自动机以及全加权自动机所定义函数的层次是严格的，从而刻画了歧义度对表达力的影响。全文以数学证明为主要评估手段，不涉及实验实现。
We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural numbers. As a corollary we show that the hierarchy of functions definable by unambiguous, finitely-ambiguous, polynomially-ambiguous weighted automata, and the full class of weighted automata is strict for the min-plus and max-plus semirings.
@article{paperbot1297,
title = {Pumping lemmas for weighted automata},
author = {Agnishom Chattopadhyay and Filip Mazowiecki and Anca Muscholl and Cristian Riveros},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 3},
year = {2021},
doi = {10.46298/lmcs-17(3:7)2021}
}