Relatively f-disjunctive languages

Fix a finite alphabet X with at least two letters. For a language L over X, the syntactic congruence of L is the \(\subseteq\)-smallest congruence \(P_ L\) on the free monoid \(X^*\) for which L is a union of classes; Syn(L) denotes the quotient \(X^*/P_ L\). L is said to be regular if Syn(L) is finite. L is dense if \(L\cap X^*wX^*\neq \emptyset\) for any \(w\in X^*\). L is bidense if both L and its complement are dense. L is disjunctive if \(P_ L\) is equality. \textit{Y. Q. Guo}, \textit{H. J. Shyr} and \textit{G. Thierrin} [Int. J. Comput. Math. 18, 219-237 (1986)] introduced the notion of an f-disjunctive language: L is f-disjunctive if each \(P_ L\)-class is finite. The authors introduce and study a generalization of these concepts, by making them relative to a dense language: they say a language is rf-disjunctive (resp. r-disjunctive) if, for some dense language D, \(| [u]_ L\cap D| <\infty\) (resp. \(| [u]_ L\cap D| \leq 1)\) for all \(u\in X^*\), where \([u]_ L\) stands for the \(P_ L\)-class of u. They say a language D is an fd-domain if, for all \(L\subseteq X^*\), \(| [u]_ L\cap D| <\infty\) for all \(u\in X^*\) implies L is f-disjunctive. The paper includes the following results. 1) Every fd-domain is dense. 2) The classes of f- disjunctive, rf-disjunctive and bidense non-regular languages form a strictly increasing \(\subseteq\)-chain. 3) The following are equivalent: a) L is r-disjunctive; b) L is rf-disjunctive; c) Syn(L) has no finite ideals.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Relatively f-disjunctive languages

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