Authors
Citation
S. Varricchio, A PUMPING CONDITION FOR REGULAR SETS, SIAM journal on computing, 26(3), 1997, pp. 764-771
Citations number
11
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
ISSN journal
00975397
Volume
26
Issue
3
Year of publication
1997
Pages
764 - 771
Database
ISI
SICI code
0097-5397(1997)26:3<764:APCFRS>2.0.ZU;2-Z
Abstract
We prove that a language of a finitely generated free monoid is regula
r if and only if it satisfies the positive block pumping property. Thi
s gives a positive answer to a problem posed by Ehrenfeucht, Parikh, a
nd Rozenberg [SIAM J. Comput., 10 (1981), pp. 536-541].