Note on Dissecting Power of Regular Languages
摘要
Let \(c>1\) be a real constant. We say that a language L is c-constantly growing if for every word \(u\in L\) there is a word \(v\in L\) with \(\vert u\vert <\vert v\vert \le c+\vert u\vert \) . We say that a language L is c-geometrically growing if for every word \(u\in L\) there is a word \(v\in L\) with \(\vert u\vert <\vert v\vert \le c\vert u\vert \) . Given a language L, we say that L is \({{\,\textrm{REG}\,}}\) -dissectible if there is a regular language R such that \(\vert L\setminus R\vert =\infty \) and \(\vert L\cap R\vert =\infty \) . In 2013, it was shown that every c-constantly growing language L is \({{\,\textrm{REG}\,}}\) -dissectible. In 2023, the following open question has been presented: “Is the family of geometrically growing languages \({{\,\textrm{REG}\,}}\) -dissectible?” For every \(c>1\) , we construct a c-geometrically growing language L that is not \({{\,\textrm{REG}\,}}\) -dissectible. Hence we answer negatively to the open question.