SOME VARIATIONS ON THE NOTION OF LOCALLY TESTABLE LANGUAGE

The aim of this paper is to complete the characterization of the languages that are Boolean combinations (of a subset) of languages of the form wA*, A*w or L(w,r,t,n), where A is an alphabet, w ∈ A⁺, r,t ≥ 0, n ≥ 1 and L(w,r,t,n) denotes the set of all words u in A⁺ such that the number of occurrences of the factor w in u is congruent to r threshold t mod n. For each class C of languages such that A+C is a Boolean algebra generated by some of the following types of languages: wA*, A*w, A*wA* = L(w,1,1,1) or L(w,r,t,1), and such that C does not constitute a variety of languages, we compute the smallest variety of languages containing C and the largest variety of languages contained in C.