A Pumping Condition for Regular Sets
Stefano Varricchio · SIAM Journal on Computing · 1997
We prove that a language of a finitely generated free monoid is regular if and only if it satisfies the positive block pumping property. This gives a positive answer to a problem posed by Ehrenfeucht, Parikh, and Rozenberg [SIAM J. Comput., 10 (1981), pp. 536--541].