
doi: 10.1007/bf02573680
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\}\).
510.mathematics, Free semigroups, generators and relations, word problems, Semigroups in automata theory, linguistics, etc., minimal right \(k\)-dense languages, maximal prefix codes, minimal right \(k\)-dense submonoids, descending chains of minimal right \(m\)- dense languages, Article, free monoids
510.mathematics, Free semigroups, generators and relations, word problems, Semigroups in automata theory, linguistics, etc., minimal right \(k\)-dense languages, maximal prefix codes, minimal right \(k\)-dense submonoids, descending chains of minimal right \(m\)- dense languages, Article, free monoids
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
