Citations
Altmetric:
Alternative Title
Abstract
Ehrenfeucht, Parikh and Rozenberg gave an interesting characterisation of the regular languages called the block pumping property. When requiring this property only with respect to members of the language but not with respect to nonmembers, one gets the notion of block pumpable languages. It is shown that these block pumpable are a more general concept than regular languages and that they are an interesting notion of their own: they are closed under intersection, union and homomorphism by transducers; they admit multiple pumping; they have either polynomial or exponential growth. © 2015 Elsevier B.V.
Keywords
Automata theory, Block pumpable languages, Block pumping lemma, Regular languages
Source Title
Theoretical Computer Science
Publisher
Elsevier
Series/Report No.
Collections
Rights
Date
2016
DOI
10.1016/j.tcs.2015.10.008
Type
Article