A Generalized Pumping Lemma for Weighted Recognizable Languages

Pumping lemmata are the main tool to prove that a certain language does not belong to a class of languages like the recognizable languages or the context-free languages. Essentially two pumping lemmata exist for the recognizable weighted languages: the classical one for the Boolean semiring (i.e., the unweighted case) and a similar one for fields. A joint generalization of these two pumping lemmata is provided that applies to all (right) Artinian semirings. These are (potentially non-commutative) semirings over which all finitely generated (right) semimodules have a finite bound on the length of chains of strictly increasing (right) subsemimodules. Since Artinian rings are exactly those that satisfy the Descending Chain Condition, the Artinian semirings include all skew fields and naturally also all finite semirings. The new pumping lemma thus covers most previously known pumping lemmata for recognizable weighted languages and a non-exhaustive list of semirings to which the new pumping lemma can be applied is provided as well.