Right \(k\)-dense languages (Q1322582)

Let \(X\) be an alphabet, \(X^*\) be the free monoid generated by \(X\) and \(X^+ = X^* \setminus \{1\}\) where 1 is the empty word. Every element of \(X^*\) is called a word over \(X\) and every subset of \(X^*\) is called a language over \(X\). In this paper, we consider only finite alphabets. A language \(L \subseteq X^*\) is said to be dense (right dense) if for every \(u \in X^*\) there exist words \(x,y \in X^*\) \((x\in X^*)\) such that \(xuy \in L\) \((ux \in L)\). A language is thin (right thin) if it is not dense (right dense). A language \(L\) is said to be complete (right complete) if the submonoid \(L^*\) generated by \(L\) is dense (right dense). In the above definition of density (right density), there are no restrictions on the choice of the words \(x\), \(y\) such that \(xuy \in L\) \((ux \in L)\). In this paper, we consider the special case of right density where a length restriction is imposed on the word \(x\). More precisely, a language \(L\) is called right \(k\)-dense, where \(k\) is a positive integer, if for every \(u \in X^*\) there exists a word \(x \in X^*\) such that \(ux \in L\) with \(|x|\leq k\). There are many interesting examples of right \(k\) dense languages; in particular, every regular right dense language is right \(k\)-dense for some positive integer \(k\). After establishing a few properties of right \(k\)-dense languages, we consider the concept of minimal right \(k\)-dense languages which is the most interesting aspect of right \(k\)-dense languages. In general a right dense language does not contain a minimal right dense language. This is no more the case for right \(k\)-dense languages, because every right \(k\)- dense language (submonoid) contains at least one minimal right \(k\)-dense language (submonoid). The case of minimal right \(k\)-dense submonoids is especially interesting, because these monoids are generated by maximal prefix codes. The existence of minimal right \(k\)-dense languages implies in particular the existence of infinite descending chains of minimal right \(m\)-dense languages with \(m \to \infty\). Furthermore, the intersection of these languages is either a prefix code, \(\emptyset\) or \(\{1\}\).