A characterization of dense languages

Let X be a finite alphabet with more than one letter. Let S be a language over X, i.e. a subset of the free monoid generated by X. Recall that a language is called disjunctive if its principal congruence \((=syntactic\) congruence) is the equality relation on \(X^*\). If S is a disjoint union of infinitely many disjunction languages, it is said to be disjunctive- splittable. On the other hand S is called dense if for every \(x\in X\), \(S\cap X^*xX^*\neq\emptyset \). The purpose of the note is to prove that S is dense iff it is disjunctive-splittable.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: A characterization of dense languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799823)