Kernels of Sub-classes of Context-Free Languages

While the closure of a language family \(\mathscr {L}\) under certain language operations is the least family of languages which contains all members of \(\mathscr {L}\) and is closed under all of the operations, a kernel of \(\mathscr {L}\) is a greatest family of languages which is a subfamily of \(\mathscr {L}\) and is closed under all of the operations. Here we investigate properties of kernels of general language families and operations defined thereon as well as kernels of (deterministic) (linear) context-free languages with a focus on Boolean operations. While the closures of language families usually are unique, this uniqueness is not obvious for kernels. We consider properties of language families and operations that yield unique and non-unique, that is a set, of kernels. For the latter case, the question whether the union of all kernels coincides with the language family, or whether there are languages that do not belong to any kernel is addressed. Furthermore, the intersection of all kernels with respect to certain operations is studied in order to identify sets of languages that belong to all of these kernels.