Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Semigroup Forumarrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Semigroup Forum
Article . 1994 . Peer-reviewed
License: Springer TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 1994
Data sources: zbMATH Open
versions View all 2 versions
addClaim

Right k-dense languages

Right \(k\)-dense languages
Authors: Ito, M.; Yu, S.S.; Thierrin, G.;

Right k-dense languages

Abstract

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\}\).

Country
Germany
Keywords

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

  • BIP!
    Impact byBIP!
    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
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
3
Average
Top 10%
Average
Green