On the Combinatorial Alphabets of a Language

The combinatorial degree (or dimension) of a language L over a finite alphabet Σ is the positive integer d(L) = min{card(A) | A ⊂ Σ*, L ⊂ A*}. A subset A of Σ* for which L ⊂ A* and card (A) = d(L) will be called a combinatorial alphabet of the language L. The set of all the combinatorial alphabets of L will be denoted by CA(L). In this paper we shall establish the main properties and the structure of CA(L) and also we shall prove that for every language L there exists a finite part Lf - which will be called, by analogy with the famous notion of a test-set, a finite combinatorial test-set - such that CA(L) = CA(Lf). We shall prove also that each language has a finite subset which is simultaneously a test-set and a combinatorial test-set, we shall highlight some relations between test-sets and combinatorial test-sets and we shall give some interesting examples.