Disjunctive splittability of languages (Q1105047): Difference between revisions

Let X be a finite alphabet with more than one element. A language A is any subset of the free monoid \(X^*\) on X. The language A is said to be dense if \(A\cap X^*uX^*\neq \emptyset\) for any \(u\in X^*\). A is discrete if \(| A\cap X^ n| \leq 1\) for any \(n\geq 1\). A is locally finite of rank r if \(| A\cap uv^+w| \leq r\) for any \(u,v,w\in X^*\), where \(B^+\) denotes the subsemigroup generated by B. A is a prefix code if u,ux\(\in A\) implies \(x=1\). For a language A, \(P_ A=A\setminus AX^+\). Consider a class T of languages containing at least one dense language and closed under taking dense subsets (e.g., the class P of all prefix codes). A language is said to be DT-splittable if it is a disjoint union of dense discrete languages in T which are locally finite of rank 1. In case \(A\setminus F\) is DT-splittable for some finite language F, A is said to be semi-DT-splittable. Starting from an extension of a result of \textit{H. J. Shyr} [Inf. Control 46, 257-269 (1980; Zbl 0453.68046)], the author investigates these notions extensively. Among other results, the following are proved in the paper. 1) A language is DT-splittable if and only if it is a union of dense languages in T. 2) A language A is DP-splittable if and only if there exist \(B,C\subseteq P_ A\) such that \(A\cap BX^*\) and \(A\cap CX^*\) contain dense prefix codes. 3) For any dense languages A, B and C, ABC is semi-DP-splittable. 4) If A is a dense language with \(1\not\in A\), then \(A^ n\) is DP-splittable for some \(n\geq 1\).