The chop of languages (Q2358686)

The contribution discusses the chop operation, which combines two words \(u\) and \(v\) into a single word \(u'w'v'\) by aligning a non-empty suffix \(w'\) of the first word \(u = u'w'\) with the same prefix of the second word \(v = w'v'\). The result is the concatenation \(u'w'v'\) of the words with the aligned part \(w'\) not repeated. In the general setup, the length of the matched suffix \(w'\) is not restricted to be maximal or minimal, but those variations of the chop are also considered. These operations are lifted to languages, i.e., sets of words, as usual by considering all possible combinations of elements from the languages. It is investigated whether the well-known language classes of the Chomsky hierarchy and the deterministic as well as linear context-free languages are closed under the various chop operations. Moreover, the closures of the regular languages under the min- and max-chop operations are further investigated. Their closure properties under the Boolean operations as well as their relation to the well-known classes are investigated. Finally, it is investigated how succinct linear context-free languages can be represented if we additionally allow chops. First it is demonstrated that the general chop of regular languages is again regular. However, this property is no longer true for the min- or max-chop operation. With these operations even non-context-free languages can be obtained as the chop of two regular languages. Moreover, more and more expressive language classes are obtained once we utilize more chops. In other words, an infinite hierarchy of language classes is obtained, where the levels correspond to the number of permitted chop operations. Otherwise, only the finite, the context-sensitive, and the recursively enumerable languages are closed under the chop operations. The closure of the regular languages under the min- or max-chop is incomparable to the other classes and exhibits nonclosure under all Boolean operations as well as a number of other common operations except for reversal. Finally, non-recursive trade-offs are demonstrated between the classes of linear context-free languages and the various chops of them. The paper is well written and should be understandable to any graduate student of computer science. A basic familiarity with language and automata theory is assumed, but all additional results are properly introduced, illustrated and proven. Illustrations and summarizing displays are generously used to help the reader. Proofs are presented in sufficient detail to convince the average reader.