A Closure Properties of Subregular Languages and Contextual Grammars with Selection

Abstract

We investigate union, intersection, concatenation, reversal, Kleene star, Kleene plus, and homomorphism for subregular languages and for the language families generated by external and internal contextual grammars with subregular selection. We use a uniform convention that permits selection over subalphabets and binary operations on languages over different alphabets. At the language level, this convention affects several closure properties, and the empty language determines the failure of star closure for comet families. For external grammars, structural restrictions on wrapping yield non-closure under intersection, concatenation, and iteration. Separate arguments establish non-closure under union and homomorphism for a broad range of selection restrictions. A regular-selection grammar shows why a natural two-branch language cannot serve as a general external union counterexample. For internal grammars, marked block languages and the compulsory availability of the empty word in certain selectors provide a common proof framework. All twenty-two internal families considered fail to be closed under union, intersection, concatenation, and arbitrary homomorphism. Reversal is governed by a transfer theorem and directional separation witnesses. Every closure property is stated as a separate lemma for one operation and one group of families; known selection-level results are transferred to our convention and cited. Three tables collect the established results and explicitly identify the cases not settled here.