Properties of annihilators of languages (Q1375907)

Let \(X\) be a finite alphabet such that \(| X|>1\), and let \(\mathcal A\) and \(\mathcal F\) be families of subsets of \(X^*\), i.e., of languages over \(X\). Let \(\circ\) be an associative binary operation on \(2^{X^*}\), e.g., the usual concatenation operation extended to subsets, or ordered concatenation (defined in the paper). Then let \[ \alpha_{\mathcal F}({\mathcal A})=\{B\subseteq X^+\mid A\circ B\in{\mathcal F},\text{ for every }A\in{\mathcal A}\}. \] Each element of \(\alpha_{\mathcal F}({\mathcal A})\) is called a right \(\mathcal F\)-annihilator of \(\mathcal A\). One can define the set of left \(\mathcal F\)-annihilators, \(\lambda_{\mathcal F}({\mathcal A})\), similarly. This paper studies properties of such annihilators for several families \(\mathcal F\) of languages. (The operation \(\circ\) used in the annihilators in most of the paper is usual concatenation.) Families of languages considered include \(\mathcal P\), the family of prefix codes; \(\mathcal D\), the family of disjunctive languages, i.e., languages whose syntactic congruence is the identity (where the syntactic congruence for a language \(L\) is \(x\equiv y\) iff \(uxv\in L\Leftrightarrow uyv\in L,\;\forall u,v\in X^*\)); \(\mathcal Q\), the family of primitive languages, i.e., languages in which every word is primitive, meaning not a proper power of any other word. Typical results include Theorem. If \(\circ\) is concatenation and if \(\mathcal F\) is closed under \(\subset\) and satisfies \(AC,BC\in{\mathcal F}\Rightarrow (A\cup B)C\in{\mathcal F}\), then \((\alpha_{\mathcal F}(A),\subseteq,\cap,\cup)\) forms a distributive lattice for all \(A\subseteq X^+\). Theorem. For all \(A\subseteq X^+\), \(A\in{\mathcal P}\Leftrightarrow\alpha_{\mathcal P}(A)={\mathcal P}\). Theorem. \(A\in{\mathcal P}\Leftrightarrow \lambda_{\mathcal P}(A)\neq\emptyset\). Theorem. If \(A\) is a thin language (e.g., finite), then \(\alpha_{\mathcal D}(A)\subseteq{\mathcal D}\) and \(\lambda_{\mathcal D}(A)\subseteq{\mathcal D}\). Theorem. If \(\mathcal A\) is a non-empty family of non-empty languages, then \(\alpha_{\mathcal D}({\mathcal A})\neq\emptyset\). Theorem. If \(Q^c=X\setminus Q\), where \(Q\) is the set of all primitive words over \(X\), then \(\alpha_{\mathcal D}(Q^c)=\lambda_{\mathcal D}(Q^c)=2^{X^+}\setminus\{\emptyset\}\). Theorem. \(\alpha_{\mathcal D}(X^+)\) is a proper subfamily of the family of all dense languages over \(X\). The paper contains numerous other technical results of a similar sort.