Note on dissecting power of regular languages

Abstract

Let $c>1$ be a real constant. We say that a language $L$ is $c$-\emph{constantly growing} if for every word $u\in L$ there is a word $v\in L$ with $|u|<|v|\le c+|u|$. We say that a language $L$ is $c$-\emph{geometrically growing} if for every word $u\in L$ there is a word $v\in L$ with $|u|<|v|\le c|u|$. Given a language $L$, we say that $L$ is $REG$-\emph{dissectible} if there is a regular language $R$ such that $|L\setminus R|=\infty$ and $|L\cap R|=\infty$. 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.