SOME VARIATIONS ON THE NOTION OF LOCALLY TESTABLE LANGUAGE
José Carlos Costa · 2000
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 is a finite word, r; t are non-negative integers, n is a positive integer 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.