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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Note on Dissecting Power of Regular Languages

  • Josef Rukavicka

摘要

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.