论文标题
为加权自动机泵送引理
Pumping lemmas for weighted automata
论文作者
论文摘要
我们为在最小半少量，最大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.
