Quasi-completely right disjunctive languages (Q909802): Difference between revisions

Let X be an alphabet and let L be a language over X. L is said to be (right) dense if L has a non-empty intersection with every principal (right) ideal of the free monoid \(X^*\) generated by X. It is (right) disjunctive if the principal (right) congruence defined by L is the equality relation. It is completely (right) disjunctive if it is infinite and every infinite subset of it is (right) disjunctive. It is quasi- completely (right) disjunctive if it is (right) dense and every (right) dense subset of it is (right) disjunctive. The original motivation for studies presented in this paper derives from the following result due to \textit{H. J. Shyr} and \textit{C. M. Reis} [Inf. Control 37, 334-344 (1978; Zbl 0376.68044)] and \textit{H. J. Shyr} [Semigroup Forum 33, 23-30 (1986; Zbl 0581.20066)]: A language is (right) dense if and only if it contains a (right) disjunctive sublanguage. - The ultimate goal is to find necessary and sufficient conditions for a (right) dense language to be (right) disjunctive. In this paper it is shown that a right dense language L is quasicompletely right disjunctive if and only if none of the languages \(x^{-1}L\cap y^{-1}L\) is right dense with \(x,y\in X^+\) distinct words such that \(\{\) x,y\(\}\) is a prefix code. This property is used to prove that a language is right dense if and only if it contains a quasi- completely right disjunctive sublanguage. These results are applied to several interesting special situations.