2023/10/21 by Rukavicka, Josef
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2310.14114
Let c>1 be a real constant. We say that a language L is c-constantly growing if for every word u∈ L there is a word v∈ L with \vert u\vert<\vert v\vert≤ c+\vert u\vert. We say that a language L is c-geometrically growing if for every word u∈ L there is a word v∈ L with \vert u\vert<\vert v\vert≤ c\vert u\vert. Given a language L, we say that L is REG-dissectible if there is a regular language R such that \vert L∖ R\vert=∞ and \vert L∩ R\vert=∞. In 2013, it was shown that every c-constantly growing language L is REG-dissectible. In 2023, the following open question has been presented: "Is the family of geometrically growing languages REG-dissectible?" We construct a c-geometrically growing language L that is not REG-dissectible. Hence we answer negatively to the open question.