Properties of annihilators of languages
type: Item
instance of: scholarly article
title: Properties of annihilators of languages
zbMATH Open document ID: 0924.20051
author: J. Ning
published in: Semigroup Forum
publication date: 1999-09-15T00:00:00Z
review text: 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)…
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1106580
zbMATH Keywords: annihilators
zbMATH Keywords: prefix codes
zbMATH Keywords: disjunctive languages
zbMATH Keywords: primitive words
zbMATH Keywords: ordered concatenation
reviewed by: William R. Nico
MaRDI profile type: Publication
full work available at URL: s00233-002-7004-4
OpenAlex ID: W2003564526
DOI: 10.1007/S00233-002-7004-4
description: scientific article; zbMATH DE number 1106580