Properties of annihilators of languages
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.
- \(d\)-minimal languages
- 2-codes and 2-code annihilators
- Sub-classes of the monoid of left cancellative languages
- scientific article; zbMATH DE number 942725 (Why is no real title available?)
- scientific article; zbMATH DE number 1394487 (Why is no real title available?)
- -reducible languages
- A note on prefix primitive words
- Prefix-primitive annihilators of languages under some operations
This page was built for publication: Properties of annihilators of languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1375907)
