On block pumpable languages

详细信息    查看全文

• 作者：Christopher Hanrui Chak^a ; ^{qornotq@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Rūsiņ&scaron ; Freivalds^b ; ^{rusins@cclu.lv" class="auth_mail" title="E-mail the corresponding author} ; Frank Stephan^a ; ^c ; ^{fstephan@comp.nus.edu.sg" class="auth_mail" title="E-mail the corresponding author} ; Henrietta Tan Wan Yik^a ; ^{u0909036@u.nus.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Block pumping lemma ; Regular languages ; Block pumpable languages ; Automata theory
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P1
• 页码：272-285
• 全文大小：484 K

文摘

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.